|
|
back to boardShow all messages Hide all messages #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 ! |
|
|