Page 1 of 1

11265 - The Sultan's Problem

Posted: Sun Sep 02, 2007 2:53 pm
by SRX
I got time limit exceed ...

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


thanks ...:)

Posted: Sun Sep 02, 2007 4:17 pm
by 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.

Re: 11265 - The Sultan

Posted: Mon Sep 03, 2007 4:03 am
by SRX
SRX wrote: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...

Posted: Mon Sep 03, 2007 4:46 am
by Jan

Posted: Wed Sep 05, 2007 2:53 pm
by 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.

Posted: Wed Sep 05, 2007 7:59 pm
by sclo
jah wrote: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.

Posted: Wed Sep 05, 2007 8:41 pm
by jah
Hi sclo,

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

Posted: Wed Sep 05, 2007 9:26 pm
by sclo
I used epsilon of 1e-7

Posted: Wed Sep 05, 2007 9:49 pm
by Jan
Here are some cases.

Input
Output

Hope these help.

Posted: Wed Sep 05, 2007 10:08 pm
by jah
I get exactly the same output but still WA. :(

I'm getting crazy with this problem.

Thanks Jan.

Re: 11265 - The Sultan

Posted: Mon Jun 20, 2011 6:39 pm
by 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.

Re: 11265 - The Sultan

Posted: Mon Jul 04, 2011 7:36 pm
by 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.

Re: 11265 - The Sultan's Problem

Posted: Thu Sep 03, 2015 10:10 pm
by 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.

Re: 11265 - The Sultan's Problem

Posted: Fri Sep 04, 2015 11:50 pm
by moe
Never mind. I finally figured it out. Thank you all for your help