| ||||||||||
| 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