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

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

Показать все сообщения Спрятать все сообщения

{$N+}
Program Ural1103;

 Type
   Tpc=record
         x,y:integer;
       End;
 Var
   n:Integer;
   c:Array[0..5000] Of Tpc;
   angle:Array[0..4999] Of extended;

 Function chaji(x1,y1,x2,y2,x3,y3:Integer):Shortint;
  Var
    d:Real;
 Begin
   d:=(x1-x3)*(y2-y3)-(x2-x3)*(y1-y3);
   chaji:=0;
   If d>0 Then chaji:=1
     Else If d<0 Then chaji:=-1;
 End;

 Procedure Init;
  Var
    i,minx,miny,bj:integer;
 Begin
   {Assign(Input,'1103.in');
   Reset(Input);}

   minx:=maxint; miny:=maxint;
   Readln(n);
   For i:=1 To n Do
   Begin
     Readln(c[i].x,c[i].y);
     If c[i].x<minx Then
     Begin
       minx:=c[i].x; miny:=c[i].y;
       bj:=i;
     End
     Else If (c[i].x=minx)And(c[i].y<miny) Then
          Begin
            miny:=c[i].y; bj:=i;
          End;
   End;
   c[0]:=c[bj]; c[bj]:=c[n];
   Close(input);

   bj:=1;
   For i:=2 To n-1 Do
     If chaji(c[0].x,c[0].y,c[bj].x,c[bj].y,c[i].x,c[i].y)=-1 Then bj:=i;
   c[n+1]:=c[1]; c[1]:=c[bj]; c[bj]:=c[n+1];
 End;

 Function distance(x1,y1,x2,y2:integer):extended;
 Begin
   distance:=sqrt(sqr(x1-x2)+sqr(y1-y2));
 End;

 Procedure Print(x,y:integer);
 Begin
   Writeln(c[0].x,' ',c[0].y);
   Writeln(c[1].x,' ',c[1].y);
   Write(x,' ',y);
 End;

 Function count_angle(x1,y1,x2,y2,x3,y3:Integer):extended;
  Var
    cos,a:extended;
 Begin
   cos:=sqr(distance(x1,y1,x2,y2))+sqr(distance(x2,y2,x3,y3))-sqr(distance(x1,y1,x3,y3));
   cos:=cos/(2*distance(x1,y1,x2,y2)*distance(x2,y2,x3,y3));

   If (cos<1e-16)And(cos>-1e-16) Then
   Begin
     a:=90;
   End
   Else
   Begin
     If cos>0 Then a:=arctan(sqrt(1-cos*cos)/cos)
     Else
     Begin
       cos:=-cos;
       a:=arctan(sqrt(1-cos*cos)/cos)+90;
     End;
   End;
   count_angle:=a;
 End;

Procedure Find;
  Var
    i,j:integer;
    s:extended;
 Begin
   For i:=2 To n-1 Do angle[i]:=count_angle(c[0].x,c[0].y,c[i].x,c[i].y,c[1].x,c[1].y);

   For i:=2 To n-2 Do
     For j:=i+1 To n-1 Do
       If angle[j]>angle[i] Then
       Begin
         s:=angle[i]; angle[i]:=angle[j]; angle[j]:=s;
         c[n]:=c[i]; c[i]:=c[j]; c[j]:=c[n];
       End;

   Print(c[(n+1)div 2].x,c[(n+1)div 2].y);
 End;

Begin
  Init;
  find;
End.
haha,I know.
I should use extended instead of integer