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

Обсуждение задачи 1062. Триатлон

Where is my mistake? WA #14
Послано DWED 16 дек 2005 14:24
uses windows;
var canwin:array[1..100] of boolean;
    a,b,c:array[1..100] of extended;
    t1,t2,mi,mc,i,j,k,m,n:integer;
    l,ml,d,x,y,z,m1,m2,m3,m4,m5,m6:extended;
label next;
begin
 randomize;
 t1:=gettickcount;
 readln(n);
 for i:=1 to n do begin
  readln(x,y,z);
  a[i]:=1/x; b[i]:=1/y; c[i]:=1/z;
 end;
 for i:=1 to n do canwin[i]:=false;

 t2:=t1;
 while t2<t1+1500 do begin
  x:=random(1000000)+1; y:=random(1000000)+1; z:=random(1000000)+1;
  ml:=a[1]*x+b[1]*y+c[1]*z; mc:=1; mi:=1;
  for m:=2 to n do begin
   l:=a[m]*x+b[m]*y+c[m]*z;
   if l<ml then begin ml:=l; mi:=m; mc:=0; end;
   if l=ml then mc:=mc+1;
  end;
  if mc=1 then canwin[mi]:=true;
  t2:=gettickcount;
 end;

 x:=1;
 for i:=1 to n do if not(canwin[i]) then begin
  for j:=1 to n-1 do if j<>i then begin
   for k:=j+1 to n do if k<>i then begin
    m1:=b[i]-b[j]; m2:=c[i]-c[j]; m3:=a[j]-a[i]-0.000000000001;
    m4:=b[i]-b[k]; m5:=c[i]-c[k]; m6:=a[k]-a[i]-0.000000000001;
    d:=m1*m5-m2*m4;
    if d<>0 then begin
     y:=(m3*m5-m6*m2)/d; z:=(m1*m6-m4*m3)/d;
     if (y>=0)and(z>=0) then begin
      ml:=a[1]*x+b[1]*y+c[1]*z; mc:=1; mi:=1;
      for m:=2 to n do begin
       l:=a[m]*x+b[m]*y+c[m]*z;
       if l<ml then begin ml:=l; mi:=m; mc:=0; end;
       if l=ml then mc:=mc+1;
      end;
      if mc=1 then canwin[mi]:=true;
      if canwin[i] then goto next;
     end;
    end;
   end;
  end;
next:;
 end;

 for i:=1 to n do if canwin[i] then writeln('Yes') else writeln('No');
end.