ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1103. Карандаши и окружности

I thick this is the correct method!
Послано crazy 11 май 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 !