858 - Berry Picking
Moderator: Board moderators
858 - Berry Picking
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?
Thanks in advance!
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?
Thanks in advance!
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!
Thanks daveon

Any other help will be greatful!
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.

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.
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:
For example, input:
My program gives:
Hope it helps. 
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:
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." )Emilio wrote:6. If the sum is greater or equal than the threshold then the ouput is "YES" otherwise "NO".
For example, input:
Code: Select all
1
4
0 0
2 0
2 2
0 2
2
1
Code: Select all
NO

-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 858 - Berry Picking
I implemented my program almost the same with your way and got A.C.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?
Thanks in advance!
The only difference which I observed from your statements is in step 3.
In step 3, two side of your big segment is decided by the MAX and MIN of vertexs but I set it directly with two very big numbers (e.q. 100000000 and -100000000). But I do think it will cause you got W.A.
After all, since the problem is well-defined, It means you don't need to check many exceptions, just do it directly.

Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?