## 858 - Berry Picking

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

Moderator: Board moderators

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

### 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!

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA
Hi,

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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Hi,

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

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA
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.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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?

Thanks in advance!

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA
You could be right, but your code is almost the same as mines except that I didn't sort.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA
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.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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!

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia
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.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 858 - Berry Picking

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!
I implemented my program almost the same with your way and got A.C.
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?
If so, you need to read Elements of Programming Interviews.