10'000 iterations - WA21
100'000 iterations - WA21
1'000'000 iterations - AC (but 0.5sec)

Made it with almost 1st submit, so I'll describe my way of avoiding "implementation hell".

First of all obvious things: x[i] -= x0, y[i] -= y0, so origin is at zero. x[n]=x[0], y[n]=y[0] to reduce amount of 'if's.

Second, all that we love with precision maths. I.e.
a == b --- fabs(a-b)<eps
a > b --- a > b + eps
a >= b --- a > b - eps
eps=1e-8 is enough here, but I did it without trigonometry

The main idea is that every segment covers some range of angles [a1;a2], so we have a set of "control points" of the form "angle;seg-i-start", "angle;set-i-end". So when you have this set of control points, segments will not change their relative order between two consecutive control points which can be checked by intersecting a ray and checking square of distance.

Now on how to avoid trigonometry in these and other problems like convex hull - just store vectors (segment endpoints). When comparing them for an "angle", first check the side. Let side=0 be the [0;pi) range - that is 'dy>0 || dy==0 && dx>0', then side=1 goes for [pi;2pi) range. Then you just compare sides, and if side is the same, check the sign of cross product for comparison. You will also need a special record for 2pi (side=2), I coded it as dx=0,dy=0, but be careful to treat it as (1,0) when raycasting later.

Now, ignore segments which contain origin in negative subplane (or on zero, i.e. no control points for them). Then the only thing to be dealt with is crossing 2pi-0 boundary. Criteria here is 'y[i]<0 && y[i+1]==0' - then it starts at (x[i];y[i]) and ends at (0;0). Or 'y[i]<0 && y[i+1]>0' then it starts at (x[i];y[i]), ends at (0;0), then starts at (1;0) and ends at (x[i+1];y[i+1]). These are just for 'angular' sorting of control points.

After that you will have first control point at (1;0) (angle=0) and last control point at (0;0) (angle=2pi). The rest is just running through them. Pick all control points which are 'equal' on that angular criteria, and process them - i.e. add/del corresponding segments to the heap according to px[i];py[i] ray intersection length for that control point. Let the next control point which is 'greater' according to angular criteria be 'j', after that pick topmost (nearest) segment from the heap, get intersection with px[i];py[i] ray, and px[j];py[j] ray (here don't forget to treat 0;0 as 1;0). After that add their cross product to the answer.

DP + sqrt-decomposition (or tree-like structure)

I think that Djkstra in graph of robot's ends will work.

13841287201 = 7^12
25937424601 = 11^10
31381059609 = 3^22
68719476736 = 2^36
152587890625 = 5^16

I think there is an error in your domino size cheking function or something similar. See your other topic for details.

The real solution is writing a "checker" for this problem, and then BFS over possible states from 2^n-1 to reach 0 (on bitmask of where it can be located). That produces a nice pattern which is always 2*(n-2), and ofc. shortest possible since it's fair BFS.
2 3 ... n-2 n-1 2 3 .... n-2 n-1 for odd N
2 3 ... n-2 n-1 n-1 n-2 ... 3 2 for even N

 for j := 3 to sqrt(n) do  will help you :)

Edited by author 17.03.2010 14:10

Thanks! :))

Спасибо)

Что-то ваши объяснения не очень логичны. Вы уверены, что именно эта логика заложена авторами задачи ?

There are two dp-approaches already described on the webboard

So I have accepted with dp
I have two dp
Stirling numbers of the second kind and factorial
Then precalculate answer array

Well, I got WA 3 during the contest but I'm pretty sure my idea is right, ahy tests ?

Did you check small dividers? ro pollard works very poorly with them

Greedy approach is fine but why output pairs with maximum number and minimum number ??

I used a max heap in which I hold pairs like, number i (index of the sign) and frequency of that sign. Each time I pop out from that heap the 2 index with maximal frequency, decrement their frequency and update the heap from their indexes.

I was sure that there is a more simplier aproach to that problem(like greedy), without using heap, but I was just 99.9% sure that with heap I will got AC, and so it was. :)