Posts Tagged 成都网络赛

HDOJ 2428 Stars

Posted by twcai in ACM/ICPC on October 22, 2008

成都网络赛第一题，比赛中是Teddy和 WYB一起A掉了。
比赛中觉得对这题挺有想法，现在拿回来做WA了20次……不过好歹是过掉了，离散化用的不多是主要原因，层出不穷的小错误也让我改到崩溃，看来我今天脑子被撞坏了。
我的做法是，先把出现的坐标值全部插入到数组中，排序后离散化，并替代原来的点的坐标，用hash标记，但是这儿有一个要注意的地方(就是我WA这么多次的原因)，原来的值一定不能丢掉，这在后面差值的比较中会用到。接着按坐标轴上从上往下，从左到右的顺序排序，然后枚举不同的两个点，看是否能够作为一个正方形的对角线，如果可以，那么看看另外两个点有没有被hash过……
贴下代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. struct node{
  5.     int i;
  6.     int j;
  7. };
  8. node d[1011];
  9. int n;
  10. int ls[2012];
  11. int tt[20100];
  12. int hash[2011][2011];
  13.  
  14. inline bool cmp(node x, node y)
  15. {
  16.     if(x.i == y.i)
  17.         return x.j < y.j;
  18.     else
  19.         return x.i > y.i;
  20. }
  21.  
  22. int main()
  23. {
  24.     int t, i, j, k, ret, cas = 0;
  25.     scanf("%d", &t);
  26.     while(t--)
  27.     {
  28.         scanf("%d", &n);
  29.         cas ++;
  30.         if(n < 4) {
  31.             for(i = 0; i < n; i++)
  32.                 scanf("%d %d", &d[i].j, &d[i].i);
  33.             printf("0n");
  34.             continue;
  35.         }
  36.         j = 0;
  37.         for(i = 0; i < n; i++)
  38.         {
  39.             scanf("%d %d", &d[i].j, &d[i].i);
  40.             ls[j++] = d[i].i;
  41.             ls[j++] = d[i].j;
  42.         }
  43.         sort(ls, ls + j);
  44.         k = 0;
  45.         memset(tt, -1, sizeof(tt));
  46.         for(i = 0; i < j; i++)
  47.         {
  48.             if(tt[ls[i] + 10000] >= 0)
  49.                 continue;
  50.             else
  51.             {
  52.                 tt[ls[i] + 10000] = k;
  53.                 ls[k] = ls[i];
  54.                 k++;
  55.             }
  56.         }
  57.         for(i = 0; i < n; i++)
  58.         {
  59.             d[i].i = tt[d[i].i + 10000];
  60.             d[i].j = tt[d[i].j + 10000];
  61.             hash[d[i].i][d[i].j] = cas;
  62.         }
  63.         sort(d, d+n, cmp);
  64.         ret = 0;
  65.         for(i = 0; i < n; i++)
  66.             for(j = i + 1; j < n; j++)
  67.             {
  68.                 if(d[i].i == d[j].i || d[i].j >= d[j].j)
  69.                     continue;
  70.                 if((ls[d[i].i] - ls[d[j].i]) != (ls[d[j].j] - ls[d[i].j]))
  71.                     continue;
  72.                 if(hash[d[i].i][d[j].j] == cas && hash[d[j].i][d[i].j] == cas)
  73.                     ret++;
  74.             }
  75.         printf("%dn", ret);
  76.     }
  77.     return 0;
  78. }

,

No Comments