把点按坐标排一下序，只枚举一个点和它右边的点

> #include "stdio.h"
> #include "stdlib.h"
> #include "math.h"
> #define INF 1000000
> int x[1000],y[1000],n;
> double agr[1000];
> int cmp(const void *p1,const void *p2){
>     if(*(double *)p1 > *(double *)p2)
>         return 1;
>     return -1;
> }
> int dfs(int k){
>      int i,j,now,max;
>      double val;
>      for(i=0,j=0;i<n;i++){
>          if(i!=k){
>             if(x[i]==x[k])
>                agr[j++]=INF;
>             else
>                agr[j++]=(double)(y[k]-y[i])/(x[k]-x[i]);
>          }
>      }
>      qsort(agr,n-1,sizeof(double),cmp);
>      now=1,max=0,val=agr[0];
>      for( i=1;i<n-1;i++){
>          if(fabs(val-agr[i])<0.000001)
>              now++;
>          else{
>              max=max>now? max:now;
>              now=1;
>              val=agr[i];
>          }
>      }
> 	 if(max<now) max=now;
>      return max;
> }
>      
>             
> int main(void)
> {
>     int  cs=1,i,max,now;
> //    freopen("in.txt","r",stdin);
> //    freopen("out.txt","w",stdout);
>     while( scanf("%d",&n)==1&&n){
>            for(i=0;i<n;i++)
>               scanf("%d %d",&x[i],&y[i]);
>          
>            for(i=0,max=0;i<n;i++){
>                 now=dfs(i);
>                 max=max>now? max:now;
>            }
>            max++;
>            if(max<4) max=0;
>            printf("Photo %d: %d points eliminated\n",cs++,max);
>     }
> 	return 0;
> }
>                           

• 这个优化真好，下次能早到更优解的点是不可能和前面的点在同一直线上的 (30) zerocool_08 2006-03-25 00:27:29
• Re:把点按坐标....排一下序，只枚举一个点和它右边的点优化后还是超时怎么办? (30) ice_lemon 2006-07-29 15:41:02