OJ Board

I'm also repeatedly getting WA, and since this seems to be very simple problem, I'm starting to suspect that i missed something ;p

Basic math assumptions that i made:
1) coordinates for center of mass for multiple objects are independent of each other (ie, Xcm does not depend on Y coordinates of ...

BTW, just as an information related to post above, I was getting WAs due to runtime error, not because of some tricky test case ;p


Also, if anyone else is doing these in PASCAL, one reason I had timeouts was that I expected FreePascal complier to behave too much like Delphi .... to avoid using ...

If you do not want to use Runtime error check, just remove define for RE_CHK - that should be your default.

If you get WA that you suspect might be RE in disguise, just define RE_CHK and resubmit ...if you now get TE instead of WA, it was RE !

Above approach turns on compiles checks for range ...

ok, here is code:


// to test for runtimes errors (RE) and turn them to TimeOuts
// hints: do not use inc/dec in your program (they skip R+)
{$DEFINE RE_CHK}

{$IFDEF RE_CHK}
{$Q+} // integer overflow checking $Q+
{$R+} // range checking $R+
{$S+} // stack checking $S+
{$ENDIF}

uses sysutils ...

I had several very unpleasant experiences with Runtime Errors (RE) being reported as Wrong Answer (WA).

Reason for those is mentioned in post about 'submitting Pascal'. It turns out that FPC does not emit error signal (at least not under Linux), so if RE occurs your program either just abort ...

// aL..aR is range in which, if playerA is on move, he can win
// bL..bR is range from which whatever playerB plays, he will end up in previous aL..aR area (thus keeping playerA in winning pos)

aL:=1; aR:=maxA; //start winning range for player A

// repeat next one untill you get aL<= L <=aR (then ...

well, i'm not using quadratic time solution to detect line crossing. solution that i used is fast enough, but it rely on same assumption that rest of my solution rely on.

as long as that assumption is correct, my intersection detection will work fast.

if that assumption is invalidated by changing ...

ah, i just found that my approach for generating polygon CAN generate self-intersecting polygons, as gvcormac suggested ;p

one simple test case would be:

1
6
0 0
0 1
1 0
1 2
2 1
2 2


anyway, it turned out that i had only slightly to modify my algorithm in order to detect if there is some line ...

i think that first part of my solution, one that generate polygon, can not generate self-intersecting one

but i will have to check that ;p

uhm... this is one of rare problems where i really start wondering if i should do them in PASCAL

after few optimisations, i finally got it to run fairly fast on my PC- even for more complicated cases with 100 lines, each around 1000 long, and with common string about 500 long. It runs fast on judge ...

one easy way to check if resulting polygon is 'simple' is to start from any point and move along lines , flagging points as you go, untill you hit already flagged point.

then you just check if in that process you flaged all points.

of course, it rely on being able to see which points are connected ...