台湾菜

HDOJ 2428 Stars

twcai • acm/icpc

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

inline bool cmp(node x, node y)
{
if(x.i == y.i)
return x.j < y.j;
else
return x.i > y.i;
}

int main()
{
int t, i, j, k, ret, cas = 0;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
cas ++;
if(n < 4) {
for(i = 0; i < n; i++)
scanf("%d %d", &d[i].j, &d[i].i);
printf("0n");
continue;
}
j = 0;
for(i = 0; i < n; i++)
{
scanf("%d %d", &d[i].j, &d[i].i);
ls[j++] = d[i].i;
ls[j++] = d[i].j;
}
sort(ls, ls + j);
k = 0;
memset(tt, -1, sizeof(tt));
for(i = 0; i < j; i++)
{
if(tt[ls[i] + 10000] >= 0)
continue;
else
{
tt[ls[i] + 10000] = k;
ls[k] = ls[i];
k++;
}
}
for(i = 0; i < n; i++)
{
d[i].i = tt[d[i].i + 10000];
d[i].j = tt[d[i].j + 10000];
hash[d[i].i][d[i].j] = cas;
}
sort(d, d+n, cmp);
ret = 0;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
if(d[i].i == d[j].i || d[i].j >= d[j].j)
continue;
if((ls[d[i].i] - ls[d[j].i]) != (ls[d[j].j] - ls[d[i].j]))
continue;
if(hash[d[i].i][d[j].j] == cas && hash[d[j].i][d[i].j] == cas)
ret++;
}
printf("%dn", ret);
}
return 0;
}

comments powered by Disqus