PKU 3512 Incidental Points
http://poj.org/problem?id=3512
1000個以下の点の座標が与えられるので、一直線上に最大いくつ並んでいるかを数えろというような問題。
O(n^3)だとどんなに頑張っても通る気がしないです。
傾きをハッシュで持つことによってO(n^2)で頑張りました。
テストケースはかなり多いようです。
ついでに入力の形式が面倒くさかったです。
typedef struct _node{ PI xy; int val; _node* next; }node; const int hashMod=30000; node*hash[hashMod]; node ent[1000]; int sz; int getval(PI in){ int ha=((in.F*67+in.S)%hashMod+hashMod)%hashMod; for(node*p=hash[ha];p;p=p->next) if(p->xy==in)return ++(p->val); node*p=hash[ha]; hash[ha]=ent+sz++; hash[ha]->next=p; hash[ha]->xy=in; return hash[ha]->val=1; } int x[1000],y[1000]; int n; char in[100]; char* pos; int ret; int getnum(){ while(!isdigit(*pos)){ if(*pos=='-'){ ++pos; return -getnum(); } ++pos; } ret=*pos++&15; while(isdigit(*pos))ret=(ret<<3)+(ret<<1)+(*pos++&15); return ret; } PI getxy(int x,int y){ if(x==0)return mp(0,1); if(y==0)return mp(1,0); int g=__gcd(x,y); x/=g; y/=g; if(x<0)x=-x,y=-y; return mp(x,y); } main(){ int k=1; while(gets(in)){ if(in[1]=='-')break; cout<<k++<<". "; n=0; while(true){ pos=in; x[n]=getnum(); y[n]=getnum(); ++n; gets(in); if(in[1]=='-')break; } int ans=2; rep(i,n){ int tans=2; memset(hash,0,sizeof(hash)); sz=0; rep(j,i) tans=max(tans,getval(getxy(x[i]-x[j],y[i]-y[j]))+1); ans=max(ans,tans); } printf("%d\n",ans); } }