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 |
对斜率进行排序,然后求最大值 ,一直WA,哪位大牛帮忙看下程序或给些测试数据啊,多谢!// 1118_LiningUp.cpp : 定义控制台应用程序的入口点。 // #include <iostream> #include "string.h" using namespace std; #define MAX 9999999999 double xl[1000]; int point[1000][2]; int Partition(int low,int high){ double temp=xl[low]; while(low<high){ while(low<high&&(xl[high]>=temp)) --high; xl[low]=xl[high]; while(low<high&&(xl[low]<=temp)) ++low; xl[high]=xl[low]; } xl[low]=temp; return low; } void Sort(int low,int high){ if(low<high){ int pt=Partition(low,high); Sort(low,pt-1); Sort(pt+1,high); } } int main(){ int n; cin>>n; while(n!=0){ int gmax=2; int m; for(int i=0;i<n;i++){ cin>>point[i][0]>>point[i][1]; } for(int i=0;i<n;i++){ m=0; int max=2; int maxtemp=2; for(int j=0;j<n;j++){ if(i!=j){ xl[m++]=(double)(point[j][1]-point[i][1])/(double)(point[j][0]-point[i][0]); } } Sort(0,m-1); for(int k=1;k<m;k++){ if((xl[k]-xl[k-1])<1e-9) maxtemp++; else { if(maxtemp>max) max=maxtemp; maxtemp=2; } } if(max>gmax) gmax=max; } cout<<gmax<<endl; cin>>n; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator