Page 1 of 1

### 858 - Berry Picking

Posted: Mon Apr 10, 2006 6:12 pm
Hi all!
I'm trying this problem but got WA!
My method is:
1. I assume that the vertex are clockwise or anti-clockwise.
2. I make all the polygon segments from the original set of vertex.
3. I make a big segment which coordinates are ((X of the vertical line over the bird flies),(MaxY of the set of vertex)) and ((X of the vertical line over the bird flies),(MinY of the set of vertex)).
4. I make a set with all the intersection points among the big segment and the set of all the segments maked from the original set of vertex.
5. I sort the set maked in fourth step by y coordinate, and let S be this set with n points, where always (n MOD 2)==0, I make sum(dist(i,i+1)) where (i MOD 2)==0, and assuming that sum is for i=0 to n-1, and dist is the distance among the points Si and Si+1.
6. If the sum is greater or equal than the threshold then the ouput is "YES" otherwise "NO".

Any mistake?
Error precision?

Posted: Thu Jun 08, 2006 3:22 am
Hi,

You can also have a line segment that goes from n-1 to 0.
Did you consider this?

Posted: Sat Jun 10, 2006 1:32 am
Hi,

Yeah! I consider that case. Thanks anyway daveon!
I don

Posted: Sat Jun 10, 2006 5:08 am
Hi Emilio,

After you sort, you have to make sure the vertical line segments you're measuring/adding are actually inside the polygon and not outside.

Posted: Sat Jun 10, 2006 5:15 pm
Hi daveon,

I think that the lines are always inside the polygon. I can't figure out any case where the vertical lines that I'm adding are outside. Could you put any test case where the vertical lines are outside?

Posted: Sat Jun 10, 2006 6:57 pm
You could be right, but your code is almost the same as mines except that I didn't sort.

Posted: Sat Jun 10, 2006 7:05 pm
Actually, I just resubmitted my old code ( took out the check for inside polygon) and got WA. After putting it back in, I got AC.

So you have to consider that the line segments may be outside the polygon.

Posted: Sat Jun 10, 2006 7:13 pm
I can't understand how you can get this without sort the intersection points. Really I don't know what is wrong in my code, because the functions to handle the segments works fine in other problems, and I can't figure out any test case where my code fails, altought maybe can be any overflow if the coordinates value is high. I'll try check this issue.

Thanks daveon !
Any other help will be greatful!

Posted: Sat Jun 10, 2006 7:19 pm
You submitted your last post while I was writting the mine one .
The fact about you are talking can be due that the polygon is not closed, but this issue haven't sense for this problem. Other reasons is not logic to me. As I commented any test cases where I must check this issue don't come to my mind.

Posted: Fri Mar 16, 2007 4:28 pm
Hi Emilio!

I just submitted this problem, I have AC. I assumed, that the vertices are in clockwise direction. I didn't assume, that the line segments are outside the polygon. But I think, the problem may be here:
Emilio wrote:6. If the sum is greater or equal than the threshold then the ouput is "YES" otherwise "NO".
The sum should be greater, not equal than the threshold. (problem description says: "The flight is considered useful if the bird flies over an extension of berries that exceeds some threshold length." )

For example, input:

Code: Select all

``````1
4
0 0
2 0
2 2
0 2
2
1
``````
My program gives:

Code: Select all

``````NO
``````
Hope it helps. ### Re: 858 - Berry Picking

Posted: Tue Nov 18, 2008 7:34 am
Emilio wrote:Hi all!
I'm trying this problem but got WA!
My method is:
1. I assume that the vertex are clockwise or anti-clockwise.
2. I make all the polygon segments from the original set of vertex.
3. I make a big segment which coordinates are ((X of the vertical line over the bird flies),(MaxY of the set of vertex)) and ((X of the vertical line over the bird flies),(MinY of the set of vertex)).
4. I make a set with all the intersection points among the big segment and the set of all the segments maked from the original set of vertex.
5. I sort the set maked in fourth step by y coordinate, and let S be this set with n points, where always (n MOD 2)==0, I make sum(dist(i,i+1)) where (i MOD 2)==0, and assuming that sum is for i=0 to n-1, and dist is the distance among the points Si and Si+1.
6. If the sum is greater or equal than the threshold then the ouput is "YES" otherwise "NO".

Any mistake?
Error precision?
After all, since the problem is well-defined, It means you don't need to check many exceptions, just do it directly. 