ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1815. Farm in San Andreas

oh I know how to solve in O(1)
Posted by Shen Yang 25 Nov 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
Re: oh I know how to solve in O(1)
Posted by Felix_Mate 25 Mar 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
Re: oh I know how to solve in O(1)
Posted by Shen Yang 25 Mar 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
Re: oh I know how to solve in O(1)
Posted by Felix_Mate 25 Mar 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
Re: oh I know how to solve in O(1)
Posted by Shen Yang 26 Mar 2018 05:05
wa on test case 2 is probably because there are two or three same points you must to consider
Re: oh I know how to solve in O(1)
Posted by Shen Yang 26 Mar 2018 07:59
deleted

Edited by author 18.04.2018 11:51
Re: oh I know how to solve in O(1)
Posted by Felix_Mate 2 Apr 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?
Re: oh I know how to solve in O(1)
Posted by Shen Yang 3 Apr 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
No subject
Posted by Felix_Mate 16 Apr 2018 18:50


Edited by author 16.04.2018 19:00
Re: oh I know how to solve in O(1)
Posted by Felix_Mate 16 Apr 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
Re: oh I know how to solve in O(1)
Posted by Shen Yang 17 Apr 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
Re: oh I know how to solve in O(1)
Posted by Felix_Mate 18 Apr 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.