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

Обсуждение задачи 1207. Медиана на плоскости

Now I have WA#7!
Послано BlackShark 3 янв 2009 01:11
var i,j,n,b2,n0,mid:integer;
x,y,al:array[1..10000] of real; num:array[1..10000] of integer;

begin
readln(n);
for i:=1 to n do begin
readln(x[i],y[i]);
num[i]:=i;
end;

n0:=1;
for i:=1 to n do begin
if x[i]<x[n0] then n0:=i;
if (x[i]=x[n0]) and (y[i]<y[n0]) then n0:=i;
end;

for i:=1 to n do
if i<>n0 then begin
if x[i]=x[n0] then al[i]:=pi/2
else al[i]:=arctan((y[i]-y[n0])/(x[i]-x[n0]))
end;

for i:=1 to n-1 do         {Sorting by angle}
for j:=i+1 to n do
if (al[j]<al[i]) and (i<>n0) and (j<>n0) then begin
b2:=num[i]; num[i]:=num[j]; num[j]:=b2; end;

for i:=1 to n div 2 do if i<>n0 then inc(mid) else inc(mid,2);
writeln(num[n0],' ',num[mid]);
end.

Edited by author 05.01.2009 13:11

Edited by author 05.01.2009 13:12
Re: Now I have WA#7!
Послано BlackShark 5 янв 2009 13:35
Sorry! I've found a very stupid bug! Now Accepted!!!
Re: Now I have WA#7!
Послано Oleg Strekalovsky [Vologda SPU] 22 апр 2009 16:29
I think your algo is O(n^2).
It's strange, that your have not get TLE...