| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
RE 搞不懂。。。。也就是n^nlogn的复杂度,算法思想也就是按照先计算出第一个点与其他所有点的斜率,进行一次排序,找出其中相同的计数,对所有的点进行相同的操作,计算出计数值最大的。代码如下。。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define max(a,b) (a>b?a:b)
#define N 1002
#define INF 100000000;
int main()
{
int n;
double x[N],y[N];
double xielv[1000];
while(scanf("%d",&n))
{
int result=0;
for(int i=0;i<n;i++)
scanf("%lf %lf",&x[i],&y[i]);
int count=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(x[i]-x[j]!=0)
xielv[count++]=(y[i]-y[j])/(x[i]-x[j]);
if(x[i]-x[j]==0)
xielv[count++]=INF;
}
sort(xielv,xielv+count);
int num=1,mx=0;
for(int j=0;j<count-1;j++)
{
if(xielv[j]==xielv[j+1])
num++;
else
{
mx=max(mx,num);
mx=num;
num=1;
}
}
result=max(result,mx);
}
cout<<result<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator