oh I know how to solve in O(1)

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)

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)

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)

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)

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)

deleted

*Edited by author 18.04.2018 11:51*

Re: oh I know how to solve in O(1)

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)

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

*Edited by author 16.04.2018 19:00*

Re: oh I know how to solve in O(1)

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)

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)

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.