Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2008-01-10 08:44:23

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Барабанная дробь...

MAXXX написав:

Я тоже использовал производную, но некоторые извращенцы (Skiminok и Dark_Dimius, например)smile делали єто векторами. В любом случае - как бы это далось классам ниже 11- не знаю.
По поводу второй...Есть куча методов...У большинства такая идея:
Бинарный поиск по Т(времени), вокруг каждого корабля строим окружность радиусом Vитое*Т и проверяем, имеют ли эти окружности общую точку. Как я это думал сделать (проверку наличия общей точки) - если общую точку имеют каждые 3 окружности то и каждые Н (хотя я не уверен). Ну  а проверить для 3 пересечение - несложно...Я реализовал неверно:(
У Skiminokа была идея про формирование выпуклой фигуры из дуг и получения решения ответа (сущ. - не сущ.) за N^2, но это слишком долго кодить.
Интерестно, есть ли метод определения за линейное время...Хотя для этой задачи было не критично, но все-таки...

Ах да, и еще одна идея решения...для каждой тройки окружностей найти точку и минимальное время про котором они имеют общую точку. От точки касания посчитать расстояние до всех остальных окружностей, получить ответ для этой точки. Ответ - минимум для таких точек. Решение получаеться сложностью N^4, есл находить минвремя и точку пересечения за О(1). Как это сделать....Я придумал только один метод, не связанный с огромными вычислениями на бумажке ( по типа нахождения координат точек пересечения от времени и т.д.). Это окружность Апполония, если кто хочет - погугулите.
Но вобще хотелось бы услышать совсем нормальный метод решения, если такой существует.

я делал поиск иначе.... ета точка точно находится на какойто окружности значит на ее дуге...
для каждой окружности заданого радиуса ищем ее пересичение с фиксированой(дугу) а потом пересечение пересичений
а фиксированую проганяем от 1 до н....
получается n^2*logT


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#27 2008-01-10 08:49:44

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Барабанная дробь...

Я думал что можно фиксировать наименьшую окружность. А когда выяснилось, что это не так....Там и так много мороки))...Разные приколы с нахождением дуги (по 2 точкам - внешняя или внутренняя дуга+всю окружность надо рассматривать на отрезке [0,Pi*4]+некоторые дуги надо удваивать на этом отрезке... ) Короче больше кодинга и дебага чем удовольствия.


ICQ 426287475

Поза форумом

 

#28 2008-01-10 09:48:08

paul
Новий користувач
Зареєстрований: 2007-11-13
Повідомлень: 8

Re: Барабанная дробь...

решение Navy через треугольники и окружности аполлония сложности N^3

чего-то 3-тур какой-то кодерский получился...

Поза форумом

 

#29 2008-01-10 09:50:39

Peace
Новий користувач
Звідки: Минск
Зареєстрований: 2008-01-10
Повідомлень: 2

Re: Барабанная дробь...

Я делал бинарный поиск по T, потом проверял все пары окружностей на пересечение. Тогда получается (N^2)*logT, только после понял, что проверка не гарантируют наличие общего пересечения...
А вот 5-ю не сдал sad
Расскажите, пожалуйста, подробно какое-нибудь из её решений.

Відредаговано Peace (2008-01-10 10:04:20)

Поза форумом

 

#30 2008-01-10 09:59:58

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Барабанная дробь...

До задачі navy - це є класична задача про три таракани.
Три таракани вибігли з одної точки з однаковою швидкістю, в різні напрямки, і через 1 хв 1-го вбили, через 2-і хв вбили другого, через 3 хв - третього.
Треба по трьом точкам A, B, C відновити точку, звідки вони вибігли.

Поза форумом

 

#31 2008-01-10 10:08:28

V@ny@
Новий користувач
Зареєстрований: 2007-12-17
Повідомлень: 13

Re: Барабанная дробь...

Продовження тараканів: Є n точок на площині, знайти таку нову точку, відстань від якої до найдальної була мінімальною.

Поза форумом

 

#32 2008-01-10 10:10:47

Phoenix_Ukraine
Новий користувач
Звідки: Дніпро
Зареєстрований: 2006-10-27
Повідомлень: 39
Вебсайт

Re: Барабанная дробь...

У тараканів швидкіст однакова, а там - це радіус описаного кола, а тут швидкості різні... sad


Час розкидати каміння минув. Настав час його громадити... (І.Білик)
Ласкаво прошу на oleksandr.org.ua!
icq: 372.682.964
http://chtyvo.org.ua/images/chtyvo_opening.gif

Поза форумом

 

#33 2008-01-10 10:30:44

paul
Новий користувач
Зареєстрований: 2007-11-13
Повідомлень: 8

Re: Барабанная дробь...

и поиск центра описанной окружности превращается в поиск точки пересечения 3-х окружностей аполлония, что, конечно, сложнее, но программируемо.

Відредаговано paul (2008-01-10 10:31:03)

Поза форумом

 

#34 2008-01-10 11:26:37

Skiminok
Новий користувач
Звідки: Киев, Украина
Зареєстрований: 2006-01-19
Повідомлень: 144
Вебсайт

Re: Барабанная дробь...

У меня лично было 2 идеи Navy...

Одну уже описали выше. Нахождение пересечения N кругов (здесь и далее пересечением N кругов называю область, каждая точка которой принадлежит всем N кругам) как области, ограниченной некоторым количеством дуг... цель, что оно состояло из одной точки. Идея за (N^2)*log(maxT)... однако писать это - лучше убиться.

Вторая повеселее. Рассматриваю все пары окружностей, для каждой из них определяю, находится ли точки их пересечения во всех остальных кругах. Подсчитываю количество всех таких точек (с учётом повторений). Если их ровно одна - ура, можно плясать.
Сложность (N^3)*log(maxT), однако пишется за час wink

Відредаговано Skiminok (2008-01-10 11:29:18)


Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
http://wwp.icq.com/scripts/online.dll?icq=282667777&img=5ICQ 282667777

Поза форумом

 

#35 2008-01-10 11:35:23

Big-Antik
Новий користувач
Звідки: Киев
Зареєстрований: 2007-11-01
Повідомлень: 20
Вебсайт

Re: Барабанная дробь...

У меня была только первая идея... и могу подтвердить слова Skiminok'a, что "однако писать это - лучше убиться." Сделать не успел т.к. идея пришла в самый последний момент - 22:30, ну я канеш попробовал... но не успел... не на полтора часа такое решение smile Т.е. я написал, но гдето баги... так и сдал, надейюсь на один-два теста smile


Кстати на счет планки: думаю 250-300

Відредаговано Big-Antik (2008-01-10 11:37:51)


«Жизнь — это просто куча всякой фигни, которая происходит». Гомер Симпсон.

Поза форумом

 

#36 2008-01-10 12:12:46

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Барабанная дробь...

Я ідею 2-у Skiminok'а я реалізовував годин 5-6, весь час находив баги sad

Поза форумом

 

#37 2008-01-10 12:18:02

Big-Antik
Новий користувач
Звідки: Киев
Зареєстрований: 2007-11-01
Повідомлень: 20
Вебсайт

Re: Барабанная дробь...

Воть вручную начитереные полученые решения 3-го тура smile
И конечно там пока только "хх" и "--" но тож интересно smile

(Ссылка в следующем моем посте - эта была не совсем правильная)

Общий зачет: всего 112 человек, которые сдали хотя бы одну задачу... wink

Відредаговано Big-Antik (2008-01-10 14:42:05)


«Жизнь — это просто куча всякой фигни, которая происходит». Гомер Симпсон.

Поза форумом

 

#38 2008-01-10 13:06:17

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Барабанная дробь...

Коли резалти . . . tongue

Поза форумом

 

#39 2008-01-10 13:23:21

Big-Antik
Новий користувач
Звідки: Киев
Зареєстрований: 2007-11-01
Повідомлень: 20
Вебсайт

Re: Барабанная дробь...

ніхто не знає smile


«Жизнь — это просто куча всякой фигни, которая происходит». Гомер Симпсон.

Поза форумом

 

#40 2008-01-10 14:14:57

RuslanSM
Новий користувач
Зареєстрований: 2006-10-20
Повідомлень: 21

Re: Барабанная дробь...

Щодо 5-ої задачі. Я розв'язував задачу таким чином :
Cпочатку проходив по всім відрізкам ламаної, для кожного відрізку вважав, що він - це дорога, по якій їде машина А з часу Т1 до часу Т2 ,час Т1 та Т2 знайти дуже легко. Потім знаходив який участок ламаної будуть проходити з часу Т1 до часу Т2 усі інші машини (назовемо їх Б), до речі це теж не складно. По черзі, для кожної з Б разбивав досліджуваний відрізок (по якому їздить машина А) на частини, що будуть рівні відрізкам, на які розіб'ється шлях машини Б. Потім для кожної пари відрізків користуючись похідною знаходив найменший час і відстань. Легко довести, що цей алгоритм працює О(н*(н+м)), але через велику кількість операцій з нецілими числами це доволі довго (на Celeron 1700 -- 2 секунди для максимального теста).
PS: за тими тестами, що виставлені на он-лайн перевірці программа 11 з 16 тестів проходить - 1 ТЛ і 4 ВА (звідки ВА здогадатися не можу).

Поза форумом

 

#41 2008-01-10 14:40:41

Big-Antik
Новий користувач
Звідки: Киев
Зареєстрований: 2007-11-01
Повідомлень: 20
Вебсайт

Re: Барабанная дробь...

Случайно заметил, что ссылка, которую давал неправильная немного. Подправил:

Школьники:
http://www2.olymp.vinnica.ua/cgi-bin/v_ … us:student
Сдавших в 3м туре хоть одну: 101

Не школьники:
http://www2.olymp.vinnica.ua/cgi-bin/v_ … atus:other
Сдавших в 3м туре хоть одну: 11

Общий зачет:
http://www2.olymp.vinnica.ua/cgi-bin/v_ … 0=filter:*
Сдавших в 3м туре хоть одну: 112

Відредаговано Big-Antik (2008-01-10 14:45:08)


«Жизнь — это просто куча всякой фигни, которая происходит». Гомер Симпсон.

Поза форумом

 

#42 2008-01-10 15:14:44

spiker
Новий користувач
Зареєстрований: 2007-10-24
Повідомлень: 24

Re: Барабанная дробь...

to RuslanSM: Де ти взяв on-line перевірку?

Поза форумом

 

#43 2008-01-10 15:38:28

RuslanSM
Новий користувач
Зареєстрований: 2006-10-20
Повідомлень: 21

Re: Барабанная дробь...

хм... Є тести на 5-у задачу smile. Я випадково помітив. І до речі лише на неї.

Поза форумом

 

#44 2008-01-10 15:39:30

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: Барабанная дробь...

В 5ой у меня алгоритм очень похож на алгоритм Руслана, и в проверке примерно то же самое: 9 из 16, тоже 4 ВА, но 3 ТЛ - видать, недооптимизировал где-то.

Поза форумом

 

#45 2008-01-10 15:40:44

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Барабанная дробь...

RuslanSM написав:

PS: за тими тестами, що виставлені на он-лайн перевірці программа 11 з 16 тестів проходить - 1 ТЛ і 4 ВА (звідки ВА здогадатися не можу).

А це випадково не тести 9,10,13,14?smile Теж 4 ВА.
Розв'язував моделюванням. Коли якась машина змінює відрізок, переперевіряємо її з усіма іншими. Відстань - корінь з параболи, мінімум - у вершині. Виключення, коли напрямки векторів рівні. Там константа. Однак, що треба врахувати: поточний час збільшується з проходженням чергових машин через вершини. Але коли підбиваємо підсумки проходження машини через відрізок, мінімум може виявитися у від'ємному відносно поточного часі. А це цілком логічно, бо перевірку ми робимо часто після досягнення моменту мінімуму, а якась машина могла пройти вершину, перевівши поточний час уперед. Отже, при перевірці точкою відліку беремо максимум з моментів проходження початку відрізків двома машинами (на яких машини знаходились до моменту перевірки).
Алгоритм перевірить все: для кожної пари машин і відрізків, по яких вони їдуть, перевірка відбудеться в момент виходу якоїсь машини зі свого відрізка або у момент закінчення часу.

Поза форумом

 

#46 2008-01-10 15:49:31

RuslanSM
Новий користувач
Зареєстрований: 2006-10-20
Повідомлень: 21

Re: Барабанная дробь...

3,11,13,14,15. А погано ,бо це свідчить про те, що проблема у нас в кодах sad

Поза форумом

 

#47 2008-01-10 15:53:23

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Барабанная дробь...

Задача №2:
Теорема Хеллі. Якщо на площині задано n опуклих фігур, і кожні три мають точку перетину, то і всі мають точку перетину.
Доводиться спочатку для n=4 (беремо 4 точки перетину фігур по 3 і розглядаємо всі можливі випадки взаємного розташування(на 1 прямій, "трикутник", опуклий-неопуклий чотирикутник). В кожному вказуємо точку, що належатиме всім чотирьом фігурам). Далі ведемо індукцію по n. Тут якраз буде використано випадок для 4-х фігур (робиться заміна перетину двох фігур на одну, застосування припущення,...).

Отже, шукаємо всі точки перетину кіл по три, і беремо максимум. Назвемо шукану точку для трійки центром псевдоописаного кола. Часткові випадки: точки на 1 прямій(просто); центр поза трикутником(тоді перетин відбудеться раніше). Пошук - пишемо три рівняння відстаней, віднімаємо. Отримаємо 2 рівняння з x,y,t^2. Виражаємо x,y через t^2 (якщо точки не на 1 прямій, то розвєязок існує). Підставляємо у вихідне рівнняння (перше, наприклад). І маємо біквадратне рівняння відносно t. Знаходимо точки і по максимуму їх перевіряєм (спочатку меншу, потім більшу).

O(n^3), але дуже багато математики: рядків 30. Не дуже швидкий, але в рамках: 0,5 сек на Athlon x2 1.8.

Код:

#include <cstdio>
#include <cmath>

//O(n^3) solution with using Helly's theorem

//maxcrd is 2000.00
#define inf 1000000000

#define min(a,b) (a<b?(a):(b))
#define max(a,b) (a>b?(a):(b))
#define sqr(a) ((a)*(a))
#define dist(x1,y1,x2,y2) (sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)))
#define uptime(x,y,x1,y1,v1,x2,y2,v2,x3,y3,v3,tt) \
{  \
    double temp=0;\
    temp=max(temp,dist(x1,y1,x,y)/v1);\
    temp=max(temp,dist(x2,y2,x,y)/v2);\
    temp=max(temp,dist(x3,y3,x,y)/v3);\
    tt=min(tt,temp);\
}

#define maxn 100

struct ship{double x,y,v;};

int main()
{
    int n,i,j,k;
    ship a[maxn];
    scanf("%d",&n);
    for(i=0;i<n;i++)
     scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].v);
    double t=0;
    double tt,x1s,y1s,x2s,y2s,x3s,y3s,a1,b1,c1,a2,b2,c2,det,x1,y1,v1,x2,y2,v2,x3,y3,v3,t1,t2,A,B,C,D;
    for(i=0;i<n;i++)
     for(j=i+1;j<n;j++)
      for(k=j+1;k<n;k++)
      {
        if(fabs((a[j].x-a[i].x)*(a[k].y-a[i].y)-(a[k].x-a[i].x)*(a[j].y-a[i].y))<1e-9)
        {
            t=max(t,dist(a[i].x,a[i].y,a[j].x,a[j].y)/(a[i].v+a[j].v));
            t=max(t,dist(a[j].x,a[j].y,a[k].x,a[k].y)/(a[j].v+a[k].v));
            t=max(t,dist(a[i].x,a[i].y,a[k].x,a[k].y)/(a[i].v+a[k].v));
        }else
        {
            x1=a[i].x; y1=a[i].y; v1=a[i].v;
            x2=a[j].x; y2=a[j].y; v2=a[j].v;
            x3=a[k].x; y3=a[k].y; v3=a[k].v;
            x1s=(v1*x2+v2*x1)/(v1+v2);
            y1s=(v1*y2+v2*y1)/(v1+v2);
            x2s=(v1*x3+v3*x1)/(v1+v3);
            y2s=(v1*y3+v3*y1)/(v1+v3);
            x3s=(v2*x3+v3*x2)/(v2+v3);
            y3s=(v2*y3+v3*y2)/(v2+v3);
            tt=inf;
            uptime(x1s,y1s,x1,y1,v1,x2,y2,v2,x3,y3,v3,tt);
            uptime(x2s,y2s,x1,y1,v1,x2,y2,v2,x3,y3,v3,tt);
            uptime(x3s,y3s,x1,y1,v1,x2,y2,v2,x3,y3,v3,tt);
            det=2*((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1));
            a1=((v1*v1-v2*v2)*(y3-y2)-(v2*v2-v3*v3)*(y2-y1))/det;
            b1=(-(y3-y2)*((x1*x1-x2*x2)+(y1*y1-y2*y2))+(y2-y1)*((x2*x2-x3*x3)+(y2*y2-y3*y3)))/det-x1;
            a2=((v2*v2-v3*v3)*(x2-x1)-(v1*v1-v2*v2)*(x3-x2))/det;
            b2=(-(x2-x1)*((x2*x2-x3*x3)+(y2*y2-y3*y3))+(x3-x2)*((x1*x1-x2*x2)+(y1*y1-y2*y2)))/det-y1;
            A=sqr(a1)+sqr(a2);
            B=2*a1*b1+2*a2*b2-v1*v1;
            C=sqr(b1)+sqr(b2);
            D=sqr(B)-4*A*C;
            if (fabs(A)<=1e-9&&fabs(B)>1e-9)
            {
                t1=-C/B;
                if (t1>=0) {tt=min(tt,sqrt(t1));}
            }
            if (D>=0&&fabs(A)>1e-9)
            {
                t1=(-B-sqrt(D))/(2*A);
                t2=(-B+sqrt(D))/(2*A);
                if (t1>=0) {tt=min(tt,sqrt(t1));}else
                if (t2>=0) {tt=min(tt,sqrt(t2));}
            }
            t=max(t,tt);
        }
      }
    printf("%.9lf\n",t);   
    return 0;
}

Відредаговано partisan (2008-01-10 15:54:30)

Поза форумом

 

#48 2008-01-10 16:00:17

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Барабанная дробь...

RuslanSM написав:

3,11,13,14,15. А погано ,бо це свідчить про те, що проблема у нас в кодах sad

Генератор:

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 m=4;
 n=20;
 v=1;
 maxcrd=10;
var
 i:smallint; 
begin
 assign(output,'patrol.in');
 rewrite(output);
 randomize;
 write(m,' ',v,' ',n);
 for i:=1 to n do
  write(' ',maxcrd*random,' ',maxcrd*random);
 writeln; 
 close(output);
end.

Розв'зок:

Код:

#include <cstdio>
#include <cmath>

#define maxn 1000
#define maxm 1000
#define maxcrd 2000000
#define inf 4000001

#define sqr(x) ((x)*(x))
#define dist(x1,y1,x2,y2) (sqrt(sqr(x1-x2)+sqr(y1-y2)))
#define min(a,b) ((a)<(b)?(a):(b))

struct point{double x,y;};

int n,m,i,j;
double v,len,gap,time,tek,mindist,mintime;
point a[maxn+2];
point start[maxm];
int pos[maxm];
double t[maxm];
double l[maxn];
point angle[maxn];//x is cos, y is sin;

inline void check(int i,int j,double left,double tek)
{
    double A,B,C,tekmin,out;
    A=v*v*(sqr(angle[pos[i]].x-angle[pos[j]].x)+sqr(angle[pos[i]].y-angle[pos[j]].y));
    B=2*v*((start[i].x-start[j].x)*(angle[pos[i]].x-angle[pos[j]].x)+(start[i].y-start[j].y)*(angle[pos[i]].y-angle[pos[j]].y));
    C=sqr(start[i].x-start[j].x)+sqr(start[i].y-start[j].y);
    if(fabs(A)<1e-9)
    {
      if(B>0) 
       tekmin=0;else
       tekmin=tek;
    }else
    {
      out=min(dist(start[i].x,start[i].y,a[pos[i]].x,a[pos[i]].y)/v,dist(start[j].x,start[j].y,a[pos[j]].x,a[pos[j]].y)/v); 
      if(-B/(2*A)<-out)
       tekmin=-out;else
      if(-B/(2*A)>tek)
       tekmin=tek;else
       tekmin=-B/(2*A);
      if (tekmin+left<0)
       tekmin=-left;
    }
    //we will use mindist <=> sqr(mindist)
    if(A*tekmin*tekmin+B*tekmin+C<mindist)
    {
      mindist=A*tekmin*tekmin+B*tekmin+C;
      mintime=left+tekmin;
    }
}

int main()
{
    mindist=1e50;
    scanf("%d%lf%d",&m,&v,&n);
    for(i=0;i<n;i++)
     scanf("%lf%lf",&a[i].x,&a[i].y);
    a[n]=a[0];
    a[n+1]=a[1];
    for(len=0,i=0;i<n;i++)
    {
        l[i]=dist(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
        angle[i].x=(a[i+1].x-a[i].x)/l[i];
        angle[i].y=(a[i+1].y-a[i].y)/l[i];
        len+=l[i];
    }
    gap=len/m;
    time=gap/v;
    start[0]=a[0];
    pos[0]=0;
    t[0]=min(l[0]/v,time);
    tek=0;
    j=0;
    for(i=0;i<n;i++)
    {
        tek+=l[i];
        if (tek>=gap-1e-9)
        {
            j++;
            pos[j]=i;
            tek-=gap;
            start[j].x=a[i].x+(l[i]-tek)*angle[i].x;
            start[j].y=a[i].y+(l[i]-tek)*angle[i].y;
            t[j]=min(dist(start[j].x,start[j].y,a[i+1].x,a[i+1].y)/v,time);
        }
    }
    tek=0;
    while(tek<=time+1e-9)
    {
      for(j=0,i=1;i<m;i++)
       if(t[i]<t[j])
        j=i;
      for(i=0;i<m;i++)
       if(i!=j)
        check(i,j,tek,t[j]);    
      for(i=0;i<m;i++)
      {
        start[i].x+=v*t[j]*angle[pos[i]].x;
        start[i].y+=v*t[j]*angle[pos[i]].y;
      }
      tek+=t[j];
      for(i=0;i<m;i++)
       if(i!=j)
        t[i]-=t[j];
      pos[j]=(pos[j]+1)%n;
      t[j]=min(l[pos[j]]/v,time+2e-9-tek);
    }
    printf("%.9lf %.9lf\n",mintime,sqrt(mindist));
    return 0;
}

Моделювання по eps (при 1e-4 досить нормально - компроміс часу і точності. 1e-5 - вже повільно):

Код:

#include <cstdio>
#include <cmath>

#define maxn 1000
#define maxm 1000
#define maxcrd 1000000
#define inf 2000001
#define eps 1e-4

#define sqr(x) ((x)*(x))
#define dist(x1,y1,x2,y2) (sqrt(sqr(x1-x2)+sqr(y1-y2)))
#define min(a,b) ((a)<(b)?(a):(b))

struct point{double x,y;};

int n,m,i,j;
double v,len,gap,time,tek,mindist,mintime;
point a[maxn+2];
point start[maxm];
int pos[maxm];
double t[maxm];
double l[maxn];
point angle[maxn];//x is cos, y is sin;

inline void check()
{
    int i,j;
    for(i=0;i<m;i++)
     for(j=i+1;j<m;j++)
      if(dist(start[i].x,start[i].y,start[j].x,start[j].y)<mindist)
      {
        mindist=dist(start[i].x,start[i].y,start[j].x,start[j].y);
        mintime=tek;
      }
}

int main()
{
    mindist=1e50;
    scanf("%d%lf%d",&m,&v,&n);
    for(i=0;i<n;i++)
     scanf("%lf%lf",&a[i].x,&a[i].y);
    a[n]=a[0];
    a[n+1]=a[1];
    for(len=0,i=0;i<n;i++)
    {
        l[i]=dist(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
        angle[i].x=(a[i+1].x-a[i].x)/l[i];
        angle[i].y=(a[i+1].y-a[i].y)/l[i];
        len+=l[i];
    }
    gap=len/m;
    time=gap/v;
    start[0]=a[0];
    pos[0]=0;
    t[0]=min(l[0]/v,time);
    tek=0;
    j=0;
    for(i=0;i<n;i++)
    {
        tek+=l[i];
        if (tek>=gap-1e-9)
        {
            j++;
            pos[j]=i;
            tek-=gap;
            start[j].x=a[i].x+(l[i]-tek)*angle[i].x;
            start[j].y=a[i].y+(l[i]-tek)*angle[i].y;
            t[j]=min(dist(start[j].x,start[j].y,a[i+1].x,a[i+1].y)/v,time);
        }
    }
    tek=0;
    check();
    while(tek<=time-eps)
    {
      for(i=0;i<m;i++)
      {
        start[i].x+=v*eps*angle[pos[i]].x;
        start[i].y+=v*eps*angle[pos[i]].y;
        if(dist(start[i].x,start[i].y,a[pos[i]+1].x,a[pos[i]+1].y)+dist(start[i].x,start[i].y,a[pos[i]].x,a[pos[i]].y)>l[pos[i]]+1e-5)
        {
          pos[i]++;
          start[i]=a[pos[i]];
        }
      }
      tek+=eps;
      check();
    }
    printf("%.9lf %.9lf\n",mintime,mindist);
    return 0;
}

Якщо все вірно у підрахунку початкових точок, то на немалій к-ті рандомних тестів все вірно.

Відредаговано partisan (2008-01-10 16:03:04)

Поза форумом

 

#49 2008-01-10 16:02:13

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Барабанная дробь...

double же тягне 12 знаків - до 15-ти.

Відредаговано partisan (2008-01-10 16:07:52)

Поза форумом

 

#50 2008-01-10 16:22:24

RuslanSM
Новий користувач
Зареєстрований: 2006-10-20
Повідомлень: 21

Re: Барабанная дробь...

хм... Андрій спробуй на 5-ій тест
1000 20 3
2 0
-5 2
-2 -4
Просто в тебе видала 2 нулі...
А в мене
0.00028494257274 0.00791038704773
2 число ніяк не нуль wink

PS: на рандомних тестах наші Неві видають однакові відповіді smile

Відредаговано RuslanSM (2008-01-10 16:31:56)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt