11265 - The Sultan's Problem

[SRX]

I got time limit exceed ...

Can anyone give me some hints to find out vertex points of area which problem asks ...


thanks ...

[jah]

I have not tried the problem yet but what I will try is the following.

Initially your region is a square (which is a convex polygon). You process each segment one by one and you partition your current convex region with this segment. This line defines two halfspaces, you eliminate all the points lying at the opposite side of the halfspace where you have the fountain and you add the two points arising from that intersection with the segment to the new convex polygon.

Hope this is correct.

[SRX]

I got time limit exceed ...

Can anyone give me some hints to find out vertex points of area which problem asks ...


thanks ...

I have tested some "simple" test cases , but still got WA,
can anyone who got ac give me some complex test cases ?

thanks...

[Jan]

Did you read this?

http://online-judge.uva.es/board/viewtopic.php?t=21148

[jah]

I'm getting tons of WA. I have tried this problem using rationals so in case the line intersects one of the vertexes of the polygon I don't get any precision errors. I used the method described above. Could you post some tricky test cases?

Thanks in advance.

[sclo]

I'm getting tons of WA. I have tried this problem using rationals so in case the line intersects one of the vertexes of the polygon I don't get any precision errors. I used the method described above. Could you post some tricky test cases?

Thanks in advance.

I would guess that you polygon cutting routine is incorrect, as I just get AC by using my code from other programs.

The algorithm is this:
iterate through all edges of the polygon in order
suppose u,v are 2 vertices. If u and v are on opposite sides of the line (u,v doesn't lie on the line) then add the intersection. Remember to always add the point u,v or both that is on the line or inside. Also, whatever you add must be in order.
At the end, remove all duplicate points, including duplicate first and last vertices if they are the same.

For this problem, there are no tricky cases, since the cutting line is guaranteed to be not coincident to any sides of the polygon. Also, the polygon after cutting would have at least 3 sides.

[jah]

Hi sclo,

I used exactly the algorithm you mentioned but I'm getting WA. How did you handle precision errors?

[sclo]

I used epsilon of 1e-7

[Jan]

Here are some cases.

Input
Output

Hope these help.

[jah]

I get exactly the same output but still WA.

I'm getting crazy with this problem.

Thanks Jan.

[howardcheng]

Any hints? I think I am using the correct algorithm (the same as what has been posted) and my output matches all of jan's output. Still WA.

[howardcheng]

Actually I used a slightly different algorithm and I did not deal with the case when the line cut through a vertex instead of a single edge. I got accepted after fixing that.

[moe]

Hi all,
So this problem is frustrating me enough that I am willing to give $100 to the first person who can give me a test case that fails. (The first person that posts the case here gets it).

Here is my code:

Code: Select all

Code removed after problem fixed.

As a hint, this fails with a polygon of area 0 (since it gets runtime error), except i couldn't figure out how to construct such a case.

I will be happy to send $100 your way via Google wallet, FB money transfer, or god-forbid, paypal.

Thanks in advance for your help. Have a great day.

[moe]

Never mind. I finally figured it out. Thank you all for your help