I thick this is the correct method!
Posted by
crazy 11 May 2002 13:28
#include<iostream.h>
#include<math.h>
#include<stdio.h>
const long max=5000;
const double pi=3.1415926;
long x[max],y[max];
double a[max];
double angle(long x1,long y1,long x2,long y2,long x3,long y3)
{
double d12,d13,d23;
double outcome;
d12=sqrt((double)(x1-x2)*(double)(x1-x2)+(double)(y1-y2)*(double)(y1-
y2));
d13=sqrt((double)(x1-x3)*(double)(x1-x3)+(double)(y1-y3)*(double)(y1-
y3));
d23=sqrt((double)(x2-x3)*(double)(x2-x3)+(double)(y2-y3)*(double)(y2-
y3));
outcome=acos((d13*d13+d12*d12-d23*d23)/(2*d13*d12));
return outcome;
}
void main()
{
long N;
long i,j;
long minx1,miny1,minx2,miny2,temp;
double temp_a;
cin>>N;
cin>>x[0]>>y[0];
minx1=x[0];
miny1=y[0];
for(i=1;i<N;i++)
{
cin>>x[i]>>y[i];
if(x[i]<minx1){
minx1=x[i];
miny1=y[i];
}else{
if(x[i]==minx1&&y[i]<miny1)
{
miny1=y[i];
}
}
}
if(N%2==0){
cout<<"No solution"<<endl;
return;
}
for(i=0;i<N;i++){if(x[i]!=minx1) break;}
minx2=x[i];
miny2=y[i];
for(i=0;i<N;i++){
if(x[i]!=minx1||y[i]!=miny1){
if((minx2-minx1)*(y[i]-miny1)>(miny2-miny1)*(x[i]-minx1)){
minx2=x[i];
miny2=y[i];
}
}
}
for(i=0;i<N;i++)
{
if((x[i]==minx1&&y[i]==miny1)||(x[i]==minx2&&y[i]==miny2)) a[i]=pi;
else
{
a[i]=angle(x[i],y[i],minx1,miny1,minx2,miny2);
}
}
for(i=0;i<N;i++) //sorting
for(j=i+1;j<N;j++)
{
if(a[i]>a[j])
{
temp_a=a[i];
a[i]=a[j];
a[j]=temp_a;
temp=x[i];
x[i]=x[j];
x[j]=temp;
temp=y[i];
y[i]=y[j];
y[j]=temp;
}
}
cout<<minx1<<" "<<miny1<<endl;
cout<<minx2<<" "<<miny2<<endl;
cout<<x[(N-3)/2]<<" "<<y[(N-3)/2]<<endl;
}
(1)first i find two points (minx1,miny1) (minx2,miny2)
two points generate a line which other points will stay
in the same side;
(2) i calculate the angle (minx1,miny1) (x[i],y[i]) (minx2,miny2)
(when(x[i],y[i])is equal to (minx1,miny1) or (minx2,miny2))
i let the angle equal to pi(the biggest possible angle)
(3)sort the angle
(4) output the (minx1,miny1) (minx2,miny2) and the midest point
except the two points;
is there any problems
i really can not find where i had make a mistake ;
and i wrong answer for about 10 times .
help me !