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