Posted on 2011-11-24 19:59
C小加 閱讀(1945)
評論(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;
}