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


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

Ви не зайшли.

#126 2008-01-11 17:55:20

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

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

sadsadsadsadsadsadsadsadsadsadsadsad
Прийдеться вчитися більше, та ще все попереду, я ж тільки 10 клас smile

Відредаговано V@ny@ (2008-01-11 17:55:32)

Поза форумом

 

#127 2008-01-11 18:04:10

Журі_Пасіхов
Гість

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

V@ny@ написав:

:(:(:(:(:(:(:(:(:(:(:(:(
Прийдеться вчитися більше, та ще все попереду, я ж тільки 10 клас :)

Ось так набагато краще. І, головне, корисніше.

 

#128 2008-01-11 19:09:04

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

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

Мне кажется, или тесты на NewGarden немного поменялись?..
Вчера сразу после показа результатов моя программа выдавала 7 AC и 9 BD, а теперь, причём если ничего в ней не менять, - 7 AC, 7 BD и 2 WA...


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

Поза форумом

 

#129 2008-01-13 16:15:42

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

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

Oracle написав:

partisan написав:

Oracle написав:

Народ в кого які тести не пройшли у Navy? В мене 17, 21, 26, 38, 60

2,17,21,26,38 - ВА. 49,57-61 - ТЛ.

Співпадає до речі.
Ти як робив? (мій розв'язок є раніше)

Мій код є вище, робив так: бінарний пошук по часу; для знаходження чи круги мають спільну точку: для кожного кола знаходив дуги, які належать решті кругів, це робив за допомогою перетину відрізків (дуги представляю в вигляді початкового кута і кінцевого кута - тому вони мають вигляд відрізка [поч.кут;кін.кут]), якщо хоч одне коло після таких перетинів містить хоч 1 дугу - значить і всі кола мають спільну точку. Цей розвязок мало схожий на твій з використанням теореми Хеллі.

А якщо перетин двох кіл лежить всередині третього? Тоді відрізки перетинатися не будуть, а спільна точка буде. Чому при перетині обов'язково буде коло, що не буде містити (повністю) перетину якихось двох інших?

Хоча мій розв'язок теж ідейно вірний, і явних глюків у написанні не бачу. А є невірні відповіді на практично ті самі тести.

Поза форумом

 

#130 2008-01-13 16:41:08

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

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

partisan написав:

Oracle написав:

Народ в кого які тести не пройшли у Navy? В мене 17, 21, 26, 38, 60

2,17,21,26,38 - ВА. 49,57-61 - ТЛ.

Співпадає до речі.
Ти як робив? (мій розв'язок є раніше)

Трохи пришвидшив - вже без таймів - ще 60й не пройшов.

Поза форумом

 

#131 2008-01-13 20:32:28

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

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

partisan написав:

А якщо перетин двох кіл лежить всередині третього? Тоді відрізки перетинатися не будуть, а спільна точка буде. Чому при перетині обов'язково буде коло, що не буде містити (повністю) перетину якихось двох інших?

Хоча мій розв'язок теж ідейно вірний, і явних глюків у написанні не бачу. А є невірні відповіді на практично ті самі тести.

саме тому я спочтаку відкидаю всі круги, які всередині містять інші (менші) круги


ICQ: 492581744

Поза форумом

 

#132 2008-01-13 21:00:41

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

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

2Oracle:
А с такими кругами тогда как?
x y r
0 0 3
6 0 3
3 0 4

Відредаговано kadr (2008-01-13 21:02:38)

Поза форумом

 

#133 2008-01-13 21:10:12

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

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

Oracle написав:

partisan написав:

А якщо перетин двох кіл лежить всередині третього? Тоді відрізки перетинатися не будуть, а спільна точка буде. Чому при перетині обов'язково буде коло, що не буде містити (повністю) перетину якихось двох інших?

Хоча мій розв'язок теж ідейно вірний, і явних глюків у написанні не бачу. А є невірні відповіді на практично ті самі тести.

саме тому я спочтаку відкидаю всі круги, які всередині містять інші (менші) круги

Я мав на увазі ситуацію, коли перетин якихось двох кіл лежить всередині третього (а самі кола ні) (наприклад, радіус всіх 1, центри 0 0; 0 1; 0 -1). Тоді перетину відрізків не буде, але перетин кіл буде.
Але не можу знайти контрприклад - завжди знаходиться якесь коло, що не містить повністю жодного такого перетину... Також поки що не можу довести.

А тести не проходять ті самі, ще й 2й звідкись взявся. Не розумію. Тестив на рандомних тестах - співпадає з твоїм.

Прохання до журі: перегляньте, будь ласка ці тести: 17,21,26,38,60. (2 - не можу знайти помилку. А має ж бути простий тест)

До речі, мій трохи оптимізований розв'язок (зараз вже не таймить):

Код:

#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 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;
    double r[maxn][maxn];
    for(i=0;i<n;i++)
     for(j=i;j<n;j++)
     {
        r[i][j]=dist(a[i].x,a[i].y,a[j].x,a[j].y);
        r[j][i]=r[i][j];
     }
    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;
            tt=min(tt,max(r[i][j]/(v1+v2),dist(x1s,y1s,x3,y3)/v3));
            tt=min(tt,max(r[i][k]/(v1+v3),dist(x2s,y2s,x2,y2)/v2));
            tt=min(tt,max(r[j][k]/(v2+v3),dist(x3s,y3s,x1,y1)/v1));
            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-13 22:46:42)

Поза форумом

 

#134 2008-01-13 23:18:53

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

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

partisan написав:

Я мав на увазі ситуацію, коли перетин якихось двох кіл лежить всередині третього (а самі кола ні) (наприклад, радіус всіх 1, центри 0 0; 0 1; 0 -1). Тоді перетину відрізків не буде, але перетин кіл буде.

Я розумію про шо ти говориш, але то тільки так здається - насправді спільна дуга буде, логічне доведення таке: 1. нехай у двох кіл немає точок перетину => ці кола або вкладені, або взагалі не перетинаються - ці випадки я розглядаю (перший - просто залишаю менший круг, другий - просто повертаю, що не існує спільної точки). 2. кола перетинаються - тоді в них є спільна дуга.
Спільна дуга має бути хоча б в одного кола, а в тесті про який ти говориш вона буде зразу в 2-ох (з 3-ох), бо коло, центр якого знаходиться посередині, буде мати великі спільні дуги з двома іншими, спробуй це намалювати (я говорю про дуги, як містяться всередині кругів, а не просто спільні точки 2-х кіл).


ICQ: 492581744

Поза форумом

 

#135 2008-01-13 23:26:57

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

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

2kadr: це той самий тест, про який говорить Андрій, тут у 1-о і 2-о кіл буде спільна дуга, яка належить відразу 3 кругам - це точка (0;0). Я ще раз кажу, що говорю тільки про дуги, які належать кругам (а не колам) і про те, шо спільна дуга має бути хоча б в одного (а не в всіх зразу) кіл.


ICQ: 492581744

Поза форумом

 

#136 2008-01-14 04:54:24

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

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

Oracle написав:

partisan написав:

Я мав на увазі ситуацію, коли перетин якихось двох кіл лежить всередині третього (а самі кола ні) (наприклад, радіус всіх 1, центри 0 0; 0 1; 0 -1). Тоді перетину відрізків не буде, але перетин кіл буде.

Я розумію про шо ти говориш, але то тільки так здається - насправді спільна дуга буде, логічне доведення таке: 1. нехай у двох кіл немає точок перетину => ці кола або вкладені, або взагалі не перетинаються - ці випадки я розглядаю (перший - просто залишаю менший круг, другий - просто повертаю, що не існує спільної точки). 2. кола перетинаються - тоді в них є спільна дуга.
Спільна дуга має бути хоча б в одного кола, а в тесті про який ти говориш вона буде зразу в 2-ох (з 3-ох), бо коло, центр якого знаходиться посередині, буде мати великі спільні дуги з двома іншими, спробуй це намалювати (я говорю про дуги, як містяться всередині кругів, а не просто спільні точки 2-х кіл).

В'їхав! Як зрозумів: береш чергове коло і перетинаєш його з рештою. І від кола залишається все менша і менша дуга, яка належить вже розглянутим (на даному кроці) кругам. Супер! Хороший розв'язок.

Відредаговано partisan (2008-01-14 04:54:55)

Поза форумом

 

#137 2008-01-14 15:25:16

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

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

2partisan: Так, ти правильно зрозумів - погодься - мало спільного з твоїм, а тести в тебе, в мене і в Руслана не проходять однакові, тому:

прохання до Журі перевірте  будь ласка 17, 21, 26, 38, 60 тести в задачі Navy - є серйозна підозра, шо вони невірні.


ICQ: 492581744

Поза форумом

 

#138 2008-01-14 17:51:15

Журі_Пасіхов
Гість

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

Oracle написав:

2partisan: Так, ти правильно зрозумів - погодься - мало спільного з твоїм, а тести в тебе, в мене і в Руслана не проходять однакові, тому:

прохання до Журі перевірте  будь ласка 17, 21, 26, 38, 60 тести в задачі Navy - є серйозна підозра, шо вони невірні.

Прохання зрозуміле. Займаємлся перевіркою. В випадку, якщо тести виявляться помилковими, буде проведено повторну перевірку задачі. Дякуємо за прискіпливість та толерантність при обговоренні проблеми.

 

#139 2008-01-14 20:53:35

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

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

partisan написав:

А тести не проходять ті самі, ще й 2й звідкись взявся. Не розумію. Тестив на рандомних тестах - співпадає з твоїм.

Прохання до журі: перегляньте, будь ласка ці тести: 17,21,26,38,60. (2 - не можу знайти помилку. А має ж бути простий тест)

в тебе не проходять тести, де є 2 корабля, наприклад такі:
2 1 1 1 3 1 1    /1.000
2 1 1 1 4 1 2    /1.000
2 1 1 1 4 1 1    /1.500
2 1 1 1 3 3 1    /sqrt(2)
2 1 1 10 4 2 1   /0.287
повезло шо він там такий тільки один smile


ICQ: 492581744

Поза форумом

 

#140 2008-01-14 23:53:42

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

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

Oracle написав:

partisan написав:

А тести не проходять ті самі, ще й 2й звідкись взявся. Не розумію. Тестив на рандомних тестах - співпадає з твоїм.

Прохання до журі: перегляньте, будь ласка ці тести: 17,21,26,38,60. (2 - не можу знайти помилку. А має ж бути простий тест)

в тебе не проходять тести, де є 2 корабля, наприклад такі:
2 1 1 1 3 1 1    /1.000
2 1 1 1 4 1 2    /1.000
2 1 1 1 4 1 1    /1.500
2 1 1 1 3 3 1    /sqrt(2)
2 1 1 10 4 2 1   /0.287
повезло шо він там такий тільки один smile

Е-Е-Е-Е.smile Логічно. Дякую. Я вважав, що n>=3 smile

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt