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

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

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

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

Oracle написав:

partisan написав:

Oracle написав:

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

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

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

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

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

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

partisan написав:

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

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

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

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)

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

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

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

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
повезло шо він там такий тільки один