ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1103. Pencils and Circles

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 !