Обсуждение @ 1815. Ферма в Сан-Андреасе @ Timus Online Judge

Jorjia Hint // Задача 1815. Ферма в Сан-Андреасе 6 окт 2018 19:50

Shen Yang oh I know how to solve in O(1) [11] // Задача 1815. Ферма в Сан-Андреасе 25 ноя 2017 12:18

it is just extend of fermat point, the angle is 2*pi/3 if it is fermat point in this problem

three angles are acos((c1*c1-c2*c2-c3*c3)/(2*c2*c3)),acos((c2*c2-c1*c1-c3*c3)/(2*c1*c3) and

acos((c3*c3-c1*c1-c2*c2)/(2*c1*c2))

how to get it ,just let two partial derivative to be zero,and square and add two equtation we can get it ,it is easy

Felix_Mate Re: oh I know how to solve in O(1) [10] // Задача 1815. Ферма в Сан-Андреасе 25 мар 2018 15:38

I can find three angles, but not optimal point. Three angles allow us to assume that the point depends of some angle (phi) and we must find min F(phi).
How you solve in O(1)? Give me hint

Shen Yang Re: oh I know how to solve in O(1) [9] // Задача 1815. Ферма в Сан-Андреасе 25 мар 2018 21:15

if we get three angles assume optimal point is O,and triangle is ABC, then let angle
OAB==theta, we can get some equations using sine theorem and divide two sine theorem euations we can solve tan(theta) then problem is solved

Felix_Mate Re: oh I know how to solve in O(1) [8] // Задача 1815. Ферма в Сан-Андреасе 25 мар 2018 23:48

Thanks. I forgott sin theorem.

Now i have WA2 (I search point in A1A2A3)

Triangle A1A2A3 and optimal point is X. XA1A3=phi, XA2A3=alfa12-phi-A3
cos(alfa12)=(c3*c3-c1*c1-c2*c2)/(2c1*c2)
...

A3X/sin(phi) = A1A3/sin(alfa13)
A3X/sin(alfa12-phi-A3) = A2A3/sin(alfa23)

=> A1A3/sin(alfa13) sin(phi) = A2A3/sin(alfa23) * [sin(alfa12-A3) cos(phi) - cos(alfa12-A3) sin(phi)]

tan(phi/2) = t

a*2t/(1+t*t) = b * (c*(1-t*t)/(1+t*t) - d*2t/(1+t*t))

=> phi = 2atan(t)
ans res=XA1*c1+XA2*c2+XA3*c3

In the second test the optimal point on the side of the triangle?
Can there be a test where A1=A2 or A1=A3 or A2=A3?

Edited by author 18.04.2018 11:18

Shen Yang Re: oh I know how to solve in O(1) [7] // Задача 1815. Ферма в Сан-Андреасе 26 мар 2018 05:05

wa on test case 2 is probably because there are two or three same points you must to consider

Shen Yang Re: oh I know how to solve in O(1) [6] // Задача 1815. Ферма в Сан-Андреасе 26 мар 2018 07:59

deleted

Edited by author 18.04.2018 11:51

Felix_Mate Re: oh I know how to solve in O(1) [5] // Задача 1815. Ферма в Сан-Андреасе 2 апр 2018 22:48

Hi! Your program on test
1
0 0
100 100
200 200
30 45 78
gives 15273.50647362942600000000 but right answer 14849.242404917499000 (optimal point is A3: A1A3*c1+A2A3*c2).

Is the optimal point always inside the triangle or on the side?

Shen Yang Re: oh I know how to solve in O(1) [4] // Задача 1815. Ферма в Сан-Андреасе 3 апр 2018 07:34

Yes,admin please add this tests, and make some more similar tests...

there are two points A[i]>=alpha[i] in this test ,so must compare these points and get min...
Edited by author 03.04.2018 07:41

Edited by author 03.04.2018 07:44

Felix_Mate No subject // Задача 1815. Ферма в Сан-Андреасе 16 апр 2018 18:50

Edited by author 16.04.2018 19:00

Felix_Mate Re: oh I know how to solve in O(1) [2] // Задача 1815. Ферма в Сан-Андреасе 16 апр 2018 18:50

Optimal point is O.
1) O=A or O=B or O=C
2) We have triangle ABC with 0<A,B,C<pi;
   We know cos(AOB), cos(AOC), cos(BOC).
   Let z1=(c3*c3-c1*c1-c2*c2)/(2*c1*c2), z2=(c2*c2-c1*c1-c3*c3)/(2*c1*c3),
       z3=(c3*c3-c1*c1-c2*c2)/(2*c1*c2).

   If |z1|>1 or |z2| >1 or |z3|>1 => optimal point is A or B or C
   Let |zi|<=1, i=1..3
   teta=AOB.
   Theorem sin: BO/sin(teta) = AB/sin(AOB) = AO/sin(teta+AOB) = k1 and
                   CO/sin(A-teta) = AC/sin(AOC) = k2.
   =>AO=k1*sin(teta+AOB), BO=k1*sin(teta), CO=k2*sin(A-teta).
    (*) We want find min{f(teta)=c1*AO+c2*BO+c3*CO} on 0<teta<A.
    Derivative f: cos(teta)*[c1*k1*cos(AOB)+c2*k1-c3*k2*cos(A)]+sin(teta)*[-c1*k1*sin(AOB)-c3*k2*sin(A)]=0 or cos(teta)*a+sin(teta)*b=0, cos(teta)=+=sqrt(sqr(b)/(sqr(a)+sqr(b)).
    Then we check 0<teta<A and update ans.

Where is mistake?
I think mistake is (*) but I can't understand why.

P.S. We can use Theorem cos with BOC and get equation with teta, but this equation is big and not obviously that we find solution.

P.S. Your code not help me.

Edited by author 16.04.2018 19:08

Shen Yang Re: oh I know how to solve in O(1) [1] // Задача 1815. Ферма в Сан-Андреасе 17 апр 2018 06:29

Does your result O point satisfy cos(AOB)==z1 cos(AOC)==z2 cos(BOC)==z3 ?
if it is satisfy I think you can AC

Felix_Mate Re: oh I know how to solve in O(1) // Задача 1815. Ферма в Сан-Андреасе 18 апр 2018 11:17

Now AC.
(*) is wrong because F(teta) not function!!!
P.S. All the time I incorrectly have considered the case when the point is lying on one of the sides of the triangle (in this case sin(AOB) or sin(AOC) or sin(BOC)=0).
I add this and AC:
if(fabs(sin(AOB))<eps && fabs(sin(AOC))<eps || fabs(sin(BOC))<eps) return inf;
   if(fabs(sin(AOB))<eps)
   {

      CO=AC*sin(A)/sin(AOC);
      AO=AC*sin(A+AOC)/sin(AOC);
      BO=BC*sin(C-(pi-A-AOC))/sin(BOC);
      return c1*AO+c2*BO+c3*CO;
   }
   if(fabs(AOC)<eps)
   {
      BO=AB*sin(A)/sin(AOB);
      AO=AB*sin(A+AOB)/sin(AOB);
      CO=BC*sin(B-(pi-A-AOB))/sin(BOC);
      return c1*AO+c2*BO+c3*CO;
   }

P.S. Delete your code, but keep the hints.

Al.Cash Why Weiszfeld Algorithm doesn't converge fast enough for this problem? (-) // Задача 1815. Ферма в Сан-Андреасе 2 фев 2015 19:59

Alex Vistyazh [Ivye School] Why WA2? [1] // Задача 1815. Ферма в Сан-Андреасе 7 авг 2013 17:02

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Good problem (+) [1] // Задача 1815. Ферма в Сан-Андреасе 26 мар 2011 02:22

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) How to make use of the FOCs for this problem? [5] // Задача 1815. Ферма в Сан-Андреасе 1 мар 2011 02:15

caoyuan9642 Keep WA #2...Help.. // Задача 1815. Ферма в Сан-Андреасе 10 фев 2011 10:05

Vit Demidenko I love Liberty City... // Задача 1815. Ферма в Сан-Андреасе 30 янв 2011 14:18

Обсуждение задачи 1815. Ферма в Сан-Андреасе