pku3512Incidental Points - honesty2008的博客

作者在 2010-08-02 21:23:50 发布以下内容

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3512

题目大意：输入一些点，求最多有几点共线。

注意：本题的输入是比较的繁琐的，需要好好的控制。特别注意的是x,y可能是负数。

因此，当输入一个减号时，不一定是这个测试样例结束。这样容易造成WA.

思路：每次把一个顶点作为起点，计算其余点与该点所形成的直线的斜率。

然后进行排序，看斜率相同的有几个，求出最多相同斜率个数max，答案便是max+1.

代码：969ms

//   0 ≤ |X|, |Y| < 1,000,000.
//   No test case has more than 1000 points

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-10;
const double INF=0xffffffff;
struct point
{ long x,y; };

bool same (double x,double y)
{  return fabs(x-y)<eps ;   }
double pp[1005];
int main()
{
    point p[1005];
    long i,j,tt,k,flag,cnt=1,max;
    char s[20],t[20]={'0'};
    while(1)
    {
        flag=0; i=0;
        gets(s);
        if(t[0]=='-'&&t[1]=='-'&&s[0]=='-'&&s[1]=='-')flag=1;
        if(flag)break;
        sscanf(s,"%ld %ld",&p[i].x,&p[i].y);i++;
        while(gets(t))
        {
            if(t[0]=='-'&&t[1]=='-')break;
            sscanf(t,"%ld %ld",&p[i].x,&p[i].y);
            strcpy(s,t);i++;
        }
        max=0;
        for(j=0;j<i;j++)
        {
            tt=0;
            for(k=j+1;k<i;k++)
            {
               if(p[k].x!=p[j].x)pp[tt++]=1.0*(p[k].y-p[j].y)/(p[k].x-p[j].x);
               //else if(j==k)pp[k]=-INF;
               else  pp[tt++]=INF;
            }
            sort(pp,pp+tt);
            int temp=1;
            for(k=1;k<tt;k++)
               if(same(pp[k],pp[k-1]))temp++;
               else { if(max<temp)max=temp; temp=1;  }
            if(max<temp)max=temp;
       }
        printf("%ld. %ld\n",cnt,max+1);cnt++;
    }
    return 0;
}