11265  The Sultan's Problem
Moderator: Board moderators
11265  The Sultan's Problem
I got time limit exceed ...
Can anyone give me some hints to find out vertex points of area which problem asks ...
thanks ...
Can anyone give me some hints to find out vertex points of area which problem asks ...
thanks ...
studying @ ntu csie
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.
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
I have tested some "simple" test cases , but still got WA,SRX wrote:I got time limit exceed ...
Can anyone give me some hints to find out vertex points of area which problem asks ...
thanks ...
can anyone who got ac give me some complex test cases ?
thanks...
studying @ ntu csie
Ami ekhono shopno dekhi...
HomePage
HomePage
I would guess that you polygon cutting routine is incorrect, as I just get AC by using my code from other programs.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.
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.

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
Re: 11265  The Sultan
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.

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
Re: 11265  The Sultan
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
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:
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 godforbid, paypal.
Thanks in advance for your help. Have a great day.
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.
I will be happy to send $100 your way via Google wallet, FB money transfer, or godforbid, paypal.
Thanks in advance for your help. Have a great day.
Last edited by moe on Fri Sep 04, 2015 11:50 pm, edited 1 time in total.
Re: 11265  The Sultan's Problem
Never mind. I finally figured it out. Thank you all for your help