题意:
给n个不同的点,问是否存在一个点使得这n个点关于它两两对称。
分析:
首先确定这个对称中心的坐标,然后对每个点哈希查找它的对称点。
代码:
//poj 2526
//sep9
#include <iostream>
using namespace std;
const int maxN=10024;
const int hashlen=1000023;
const int mod=40013;
struct Point
{int x,y;
}p[maxN];
struct Node
{int index,x,y,next;
}a[maxN+10];int n,e;
int hash_list[hashlen+10];int hash_value(int x,int y)
{x%=mod,y%=mod;return ((x*x)%mod+(y*y)%mod+(x+y)%mod+hashlen)%hashlen;
}void insert(int i)
{int v=hash_value(p[i].x,p[i].y); a[e].x=p[i].x;a[e].y=p[i].y;a[e].next=hash_list[v];hash_list[v]=e++;
}bool find(int x0,int y0)
{int v=hash_value(x0,y0); for(int i=hash_list[v];i!=-1;i=a[i].next)if(a[i].x==x0&&a[i].y==y0)return true;return false;
}int main()
{int cases;scanf("%d",&cases);while(cases--){scanf("%d",&n);int minx,miny,maxx,maxy;minx=miny=INT_MAX;maxx=maxy=INT_MIN;memset(hash_list,-1,sizeof(hash_list));e=0;for(int i=0;i<n;++i){scanf("%d%d",&p[i].x,&p[i].y);insert(i);if(p[i].x<=minx){if(p[i].x==minx)miny=min(miny,p[i].y);else{minx=p[i].x;miny=p[i].y;}}if(p[i].x>=maxx){if(p[i].x==maxx)maxy=max(maxy,p[i].y);else{maxx=p[i].x;maxy=p[i].y;}}}int target_x=maxx+minx;int target_y=maxy+miny;bool ok=true;for(int i=0;i<n;++i)if(find(target_x-p[i].x,target_y-p[i].y)==false){ok=false;break;}printf("%s\n",ok==true?"yes":"no");}return 0;
}