11265 - The Sultan's Problem

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

11265 - The Sultan's Problem

Post by SRX » Sun Sep 02, 2007 2:53 pm

I got time limit exceed ...

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


thanks ...:)
studying @ ntu csie

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Sun Sep 02, 2007 4:17 pm

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
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: 11265 - The Sultan

Post by SRX » Mon Sep 03, 2007 4:03 am

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...
studying @ ntu csie

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 03, 2007 4:46 am

Ami ekhono shopno dekhi...
HomePage

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Wed Sep 05, 2007 2:53 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Sep 05, 2007 7:59 pm

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.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Wed Sep 05, 2007 8:41 pm

Hi sclo,

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Sep 05, 2007 9:26 pm

I used epsilon of 1e-7

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 05, 2007 9:49 pm

Here are some cases.

Input
Output

Hope these help.
Ami ekhono shopno dekhi...
HomePage

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Wed Sep 05, 2007 10:08 pm

I get exactly the same output but still WA. :(

I'm getting crazy with this problem.

Thanks Jan.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 11265 - The Sultan

Post by howardcheng » Mon Jun 20, 2011 6:39 pm

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

Re: 11265 - The Sultan

Post by howardcheng » Mon Jul 04, 2011 7:36 pm

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
New poster
Posts: 2
Joined: Thu Sep 03, 2015 10:04 pm

Re: 11265 - The Sultan's Problem

Post by moe » Thu Sep 03, 2015 10:10 pm

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.
Last edited by moe on Fri Sep 04, 2015 11:50 pm, edited 1 time in total.

moe
New poster
Posts: 2
Joined: Thu Sep 03, 2015 10:04 pm

Re: 11265 - The Sultan's Problem

Post by moe » Fri Sep 04, 2015 11:50 pm

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

Post Reply

Return to “Volume 112 (11200-11299)”