PKU 2780 Linearity
http://poj.org/problem?id=2780
n個の点が与えられる。
一直線上に並んでいる最大の点の数はいくつかを答えろというような問題。
定数を落として全探索すると面倒くさいことをしなくてもギリギリ通るようです。
int x[1000],y[1000]; int ret,c; int getnum(){ while(!isdigit(c=getchar())); ret=c&15; while(isdigit(c=getchar()))ret=(ret<<3)+(ret<<1)+(c&15); return ret; } main(){ int n; while(~scanf("%d",&n)){ rep(i,n){ x[i]=getnum(); y[i]=getnum(); } int ans=2; rep(i,n){ rep(j,i){ int tans=2; int tx=x[i]-x[j]; int ty=y[i]-y[j]; rep(k,j) if((y[k]-y[j])*tx==ty*(x[k]-x[j]))++tans; ans=max(ans,tans); } } printf("%d\n",ans); } }