Posted on 2011-11-24 19:59
C小加 阅读(1871)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题意：
给出n个点的整数坐标(n<=700)，求一条直线，使得在这条直线上的点数最多，输出点数。
思路：
简单几何题。采用几何中三个点是否在一条直线判定定理。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct
{
int x,y,count;
}Point;
Point p[703];
double a[703];
int main()
{
//freopen("input.txt","r",stdin);
int n;
while(cin>>n,n)
{
int i;
for(i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y;
}
int temp,max=0;
for(i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
temp=0;
for(int k=j+1;k<n;k++)
{
int a=(p[i].x-p[k].x)*(p[j].y-p[k].y);
int b=(p[i].y-p[k].y)*(p[j].x-p[k].x);
if(a==b) temp++;
}
max=max>temp?max:temp;
}
}
cout<<max+2<<endl;
}
return 0;
}