Show all threads Hide all threads Show all messages Hide all messages |
Hint | Jorjia | 1815. Farm in San Andreas | 6 Oct 2018 19:50 | 1 |
Hint Jorjia 6 Oct 2018 19:50 I can't solve it, yet. But i think that, it solviable as fermat point geometry construction (see wiki), and using angles, as Shen Yang suggested <AOB = acos((c1*c1-c2*c2-c3*c3)/(2*c2*c3)), <AOC = acos((c2*c2-c1*c1-c3*c3)/(2*c1*c3) and <BOC = acos((c3*c3-c1*c1-c2*c2)/(2*c1*c2)) . (c1,c2,c3 - are prices). In wiki fermat point: constructed triangles ABC' , BCA' and CAB' where <ABC' = 60, <BAC' = 60, <CBA' = 60, <BCA' = 60, and <ACB' = 60, <CAB' = 60.
Fermat point X - is intersection of AA' and BB' and CC' lines. In there, we must construct triangles ABC' , BCA', and CAB' , with <ABC' = <BAC' = <AOB / 2 <BCA' = <CBA' = <COB / 2 <ACB' = <CAB' = <AOC / 2 and intersection of AA' , BB' and CC' - will be ans, iff it's in ABC triangle. otherwice A, B, or C will be ans. |
oh I know how to solve in O(1) | Shen Yang | 1815. Farm in San Andreas | 18 Apr 2018 11:17 | 12 |
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 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 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 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 wa on test case 2 is probably because there are two or three same points you must to consider deleted Edited by author 18.04.2018 11:51 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? 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 Edited by author 16.04.2018 19:00 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 Does your result O point satisfy cos(AOB)==z1 cos(AOC)==z2 cos(BOC)==z3 ? if it is satisfy I think you can AC 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. |
Why Weiszfeld Algorithm doesn't converge fast enough for this problem? (-) | Al.Cash | 1815. Farm in San Andreas | 2 Feb 2015 19:59 | 1 |
Edited by author 02.02.2015 20:11 |
Why WA2? | Alex Vistyazh [Ivye School] | 1815. Farm in San Andreas | 10 Aug 2013 21:39 | 2 |
Why WA2? Alex Vistyazh [Ivye School] 7 Aug 2013 17:02 I can't find my mistake... Please give me second test. Sorry, but i find my mistake and i have AC :) |
Good problem (+) | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1815. Farm in San Andreas | 9 Mar 2012 13:41 | 2 |
Thanks to author - to solve it, you need math and you need coding Edited by author 26.03.2011 03:45 I agree, but how solve it fast? In my solution two binary searches and a lot of sin, cos, sqrt, etc.. so it works not fast |
How to make use of the FOCs for this problem? | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1815. Farm in San Andreas | 4 Mar 2011 11:51 | 6 |
We can write some FOCs which describe optimal point. But how to find point which satisfies these FOCs? I suspect it is not necessary to find this point, you can get correct answer without knowing exact location of it. I haven't solved this problem yet, so it is a hypotesis only... Haven't ACed yet, but it seems I found the algo which uses 2 binary searches only. If you want to use BS, you should have a sorted structure. What is it? Do you serach this point on some fixed line? Of course, I convert initial problem to some other problem, and there it is ordered structures =) Convex structure also gives O(lg n). For example golden proportion search om segment. |
Keep WA #2...Help.. | caoyuan9642 | 1815. Farm in San Andreas | 10 Feb 2011 10:05 | 1 |
What's wrong with #2? I've got 10+ WAs and found no real mistake yet.. |
I love Liberty City... | Vit Demidenko | 1815. Farm in San Andreas | 30 Jan 2011 14:18 | 1 |
|