858 - Berry Picking

[Emilio]

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]

Hi,

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

[Emilio]

Hi,

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

[daveon]

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]

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]

You could be right, but your code is almost the same as mines except that I didn't sort.

[daveon]

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]

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]

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]

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:

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]

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.