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

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

Why Wrong Answer?
Послано Koala 7 фев 2003 11:41
program p1103;

const
  maxn=5000;
  zero=1e-5;

type
  ptype=record
    x,y:longint;
  end;

var
  p:array [1..maxn] of ptype;
  n,i,j,x1,y1,x2,y2,inside,outside:longint;
  d,x,y,r:real;
  tp:ptype;

  function dis(x1,y1,x2,y2:real):real;
  begin
    dis:=sqrt(sqr(x1-x2)+sqr(y1-y2));
  end;

  procedure getcircle(x1,y1,x2,y2,x3,y3:longint; var x,y,r:real);
  var
    a1,b1,c1,a2,b2,c2:longint;
  begin
    a1:=x1-x2; b1:=y1-y2; c1:=x2*x2+y2*y2-x1*x1-y1*y1;
    a2:=x1-x3; b2:=y1-y3; c2:=x3*x3+y3*y3-x1*x1-y1*y1;
    x:=(b2*c1-b1*c2)/(a1*b2-a2*b1);
    y:=(a1*c2-a2*c1)/(a1*b2-a2*b1);
    x:=-x/2; y:=-y/2;
    r:=dis(x,y,x1,y1);
  end;

begin
  read(n);
  for i:=1 to n do read(p[i].x,p[i].y);

  for i:=2 to n do
    if p[i].y<p[1].y then
    begin
      tp:=p[1]; p[1]:=p[i]; p[i]:=tp;
    end;
  for i:=3 to n do
    if p[i].y<p[2].y then
    begin
      tp:=p[2]; p[2]:=p[i]; p[i]:=tp;
    end;

  x1:=p[1].x; y1:=p[1].y; x2:=p[2].x; y2:=p[2].y;
  for i:=3 to n do
  begin
    getcircle(x1,y1,x2,y2,p[i].x,p[i].y,x,y,r);
    inside:=0; outside:=0;
    for j:=1 to n do
    begin
      d:=dis(x,y,p[j].x,p[j].y);
      if d<r-zero then inc(inside);
      if d>r+zero then inc(outside);
    end;
    if inside=outside then
    begin
      writeln(x1,' ',y1);
      writeln(x2,' ',y2);
      writeln(p[i].x,' ',p[i].y);
      exit;
    end;
  end;

  writeln('No solution');
end.