HDU 5738 Eureka(极角排序)
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5738
【题目大意】
给出平面中一些点,在同一直线的点可以划分为一个集合,问可以组成多少包含元素不少于2的集合。
【题解】
最重要的还是处理点重合,和线重复计算的问题,对于每个点,进行极角排序,作为端点,然后统计包含它的每个集合即可。思路非常简单,然而比赛的时候……一脸懵逼地用map,pair,然后转战hash。看起来对于计算几何的敏感度还有待加强。
【代码】
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; const int N=1010,mod=1e9+7; int T,pw[N],n,ans; struct Point{ int x,y; Point(){} Point(int _x,int _y):x(_x),y(_y){} Point operator - (const Point &p){return Point(x-p.x,y-p.y);} bool operator < (const Point &p)const{return x<p.x||(x==p.x&&y<p.y);} bool operator == (const Point &p){return x==p.x&&y==p.y;} void reduce(){int g=__gcd(abs(x),abs(y));if(g)x/=g,y/=g;} }p[N],q[N]; int main(){ scanf("%d",&T);pw[0]=1; while(T--){ scanf("%d",&n);ans=0; for(int i=0;i<n;i++){ pw[i+1]=pw[i]*2%mod; scanf("%d%d",&p[i].x,&p[i].y); }sort(p,p+n); for(int i=0;i<n;i++){ int m=0,cnt=0; for(int j=i+1;j<n;j++){ if(p[j]==p[i])cnt++; else q[m++]=p[j]-p[i]; }for(int j=0;j<m;j++)q[j].reduce(); sort(q,q+m);ans=(ans+pw[cnt]-1)%mod; for(int x=0,y;x<m;x=y){ for(y=x;y<m&&q[x]==q[y];y++); ans=(ans+(long long)pw[cnt]*(pw[y-x]-1)%mod)%mod; } }printf("%d\n",ans); }return 0; }