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

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