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);
  }
}