Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对斜率进行排序,然后求最大值 ,一直WA,哪位大牛帮忙看下程序或给些测试数据啊,多谢!

Posted by GaryLiang at 2009-11-02 20:34:02 on Problem 1118
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator