137 - Polygons

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

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I've test it for several test case(I even write a prgram to grenate,but I always get WA.Can someone give me some special test case?

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Problem 137 ---- need help !!

The problem is very difficult !

Is there any algorithm that I can use to solve this problem?

Can you give me some tips?

Thanks!

ivec
New poster
Posts: 8
Joined: Tue May 27, 2003 2:41 pm
Contact:

hints for 137

The idea is to find all intersections between segments of each polygon.
There is an O(N) way to do it ( "rotating calipers" ).
But for this problem, the O(N2) brute-force approach (testing all segment pairs) will do.

When calculating intersections, also make sure to store the direction of the crossing. This will tell you which polygon is inside after ther crossing.

Then you construct the intersection polygon, going from crossing to crossing, by following the inner polygon segments after each crossing.

Some mentioned that segment intersection is a difficult problem.
Here's the routine I use (twice, to do check that each line intersects within the other segment):
[c]
typedef float Coord;
typedef struct { Coord x, y; } Pt;

enum { eLeftRight = 1, eRightLeft = 2 };
/* Intersect line a-b with segment c-d --> non-zero if exists
NB: - c is part of segment c-d, but d is not (--> next segment)
- parallel segments never intersect
Return:
0 if no intersection
eLeftRight if c-d crosses a-b left to right
eRightLeft if c-d crosses a-b right to left
*/
int intersectLineSeg( Pt* a, Pt* b, Pt* c, Pt* d, Pt* xing )
{
/* p=(px,py) is a vector perpendicular to a-b */
Coord px = a->y-b->y, py = b->x-a->x; /* + = right of a-b */
/* dot(p,ac), dot(p,ad) = k*signed distance to a-b */
Coord wc = px*(c->x-a->x) + py*(c->y-a->y);
Coord wd = px*(d->x-a->x) + py*(d->y-a->y);
Coord inv;
if( wd==0 /* d is exactly on segment */
|| ( wc!=0 && ( wc<0 == wd<0 ) ) /* c&d are on same side */
) return 0;
inv = 1.0f /(wc-wd);
/* interpolate between c&d to get intersection point */
xing->x = ( wc*d->x - wd*c->x )*inv;
xing->y = ( wc*d->y - wd*c->y )*inv;
return (wd<0) ? eLeftRight : eRightLeft ;
}
[/c]
This will do for the segment intersection, but there are a few special cases to handle during the construction of the intersection (tangeant, disjoint, or inset polygons, reordering double intersections on a single segment, etc...).

Here are some test inputs and results I used:

Code: Select all

``````  3   0 1  3 4  6 1    3  0 3  6 3  3 0
6.00
4  0 0 0 10 10 10 10 0     4  2 2 2 7 7 7 7 2
75.00
4  2 2 2 7 7 7 7 2    4  0 0 0 10 10 10 10 0
75.00
4  0 0 0 10 10 10 10 0   4  0 0 0 5 5 5 5 0
75.00
``````
hth -- Ivan

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

137 - Polygons

I'm tired with this problem. Everything seems fine, test cases that I type in are solved well, but somehow I receive WA.
Is there any tricky input that I should care for? On the board I've found one test, but my program solved it correctly.

Regards

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
After few days struggle I found the mistake and got AC. I was quite blind and the test case that revealed it was

2 5 10 10 11
2 16 4 10 16
0

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

I got WA on this problem. I guess I need more sample input and output. I would be gratefully for any help.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Not sure how meaningful this input is, but it was what I had in my input file. Input:

Code: Select all

``````6  6 3  8 2  8 1  4 1  4 2  5 3
4  1 2  1 4  5 4  5 2
6  6 3  8 2  8 1  4 1  4 2  5 3
5  1 2  1 4  5 4  5 3 4 2
5  1 2  1 4  5 4  5 3 4 2
6  6 3  8 2  8 1  4 1  4 2  5 3
6  6 3  8 2  8 1  4 1  4 2  5 3
6  1 2  1 4  5 4  5 3 4 3 4 2
6  1 2  1 4  5 4  5 3 4 3 4 2
6  6 3  8 2  8 1  4 1  4 2  5 3
4  0 1  0 2  3 2  3 1
4  1 0  1 3  2 3  2 0
4  1 0  1 3  2 3  2 0
4  0 1  0 2  3 2  3 1
4  1 0  1 3  2 1  2 0
4  0 1  0 2  3 2  3 1
4  0 1  0 2  3 2  3 1
4  1 0  1 3  2 1  2 0
0``````
Output:

Code: Select all

``   13.50   14.00   14.00   13.50   13.50    4.00    4.00    3.50    3.50``

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
thank you Per for your input, I found 1 mistake in my code

but then, I see that for input 4 and 5, the polygon is not convex, and I cannot figure out why the answer is 13.50 for both of them ?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
A very easy way of doing this is to find the intersection area, then with area of polygon a and area of polygon b, you can use:

answer = a + b - (intersection_area*2)

to find intersection area, you can simply find the polygon that comprises that area.

as a hint, that polygon is CONVEX.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
Thank you junbin, for your explanation...

Can you give me more sample input and output ... ? I really need that

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Sorry I took so long.. forgot to check this thread. :p

Anyway, I don't have my old test data anymore.. but if you provide me with the data, I can run it through my program. Also, do a search on this forum for the question number.. there is a few other threads and some of them contain some test data... if I remember right, there is this thread with only 5 test data.. but all of them are boundary cases and helped me found a tricky little bug.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
I guess I have to bother you later again if this input doesn't show my mistake , I generate it randomly ...

[cpp]
12 66 4 2 12 4 82 8 92 21 96 79 99 97 96 99 95 99 68 98 23 86 14 71 5
8 88 2 4 30 5 47 19 85 28 96 86 99 99 82 95 29
6 56 19 24 24 4 70 16 82 43 82 71 37
6 47 7 10 22 3 37 34 68 89 44 79 8
3 1 9 6 18 63 22
3 32 36 26 54 66 91
8 72 3 22 5 18 9 7 44 26 98 80 95 94 52 97 8
11 50 11 28 16 8 21 1 57 9 69 11 71 34 93 49 96 74 99 99 87 79 18
11 48 6 20 8 2 13 2 52 13 64 33 84 42 90 59 99 90 73 93 18 80 8
10 69 3 9 3 2 22 8 81 13 99 59 94 86 89 96 85 96 59 93 27
11 44 1 9 4 7 23 1 89 23 98 79 98 90 86 94 75 96 30 89 5 81 4
11 47 1 27 3 4 7 3 57 3 93 49 97 91 90 98 80 98 30 96 19 93 4
7 26 8 12 38 11 69 11 96 44 91 99 77 96 21
4 55 1 2 29 1 78 96 94
13 64 4 42 7 17 11 7 16 6 38 11 77 20 91 28 94 50 99 93 93 96 92 96 88 87 16
12 37 4 14 7 4 76 41 96 44 67 44 67 53 93 85 98 89 97 98 89 98 58 91 10
13 51 2 4 2 3 14 1 38 5 90 22 95 38 96 54 96 71 95 89 84 99 72 98 9 95 5
15 6 2 3 34 5 71 7 96 17 98 36 78 35 75 35 75 54 96 67 96 96 94 99 75 95 34 86 17 71 3
8 94 2 9 12 7 19 3 33 8 99 33 96 52 90 97 71
10 90 6 37 6 13 19 10 23 1 51 12 77 27 90 48 97 81 87 93 53
5 6 3 20 97 38 96 69 87 90 28
6 80 9 35 17 21 64 14 94 61 90 96 83
9 12 2 9 19 2 72 3 81 5 84 20 94 74 83 88 67 59 4
7 23 3 13 3 2 91 18 91 89 90 91 52 88 14
7 45 1 32 43 25 91 55 98 77 79 87 44 87 8
9 36 1 22 3 1 82 9 97 68 99 92 95 94 75 81 38 68 17
10 61 1 3 11 9 96 15 99 43 99 97 95 98 63 94 14 91 9 80 6
8 67 2 14 2 5 12 1 89 24 98 75 99 98 97 99 11
1 35 63
1 57 90
9 35 1 9 8 3 37 16 95 91 99 96 97 99 59 96 26 89 4
12 45 2 29 2 6 4 3 9 2 91 26 97 60 95 76 91 83 89 96 56 94 13 81 4
8 54 2 7 45 8 82 14 93 37 98 92 89 98 69 90 3
10 7 2 5 68 19 81 38 96 89 95 98 94 95 34 72 7 52 5 27 3
9 87 2 57 5 19 12 7 18 5 73 12 99 86 82 89 73 93 17
10 71 4 34 4 5 26 2 68 11 98 73 98 92 86 96 79 94 28 88 7
8 86 13 30 21 21 27 17 55 27 72 36 87 50 81 71 61
5 43 19 27 27 4 58 98 97 97 23
8 22 2 4 5 7 32 13 65 21 71 79 92 92 38 87 3
5 4 6 12 55 51 84 96 35 91 9
0
[/cpp]

thank you for your attention

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
1639.87 2568.05 717.50 2109.92 1692.83 725.81 2777.31 802.16 619.58 1332.75 2248.29 1540.76 3641.56 776.28 0.00 1253.74 1953.81 1199.71 2517.67 1496.87

Generally speaking, for geometry questions, random data don't help a lot... the boundary cases are those that really test the data since if they work, the cases in the middle usually will work.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
firstly, I want to thank you for your reply. It did help me a lot.

I have fixed main bug in my code.

But, afterall, my output doesn't match with yours. Moreover, I didn't expect 717.50 as the output for the third test case. because the answer should be 0.00.

Is this a mistake or I had missed something ???

[cpp]
1639.87 2568.05 0.00 2109.92 1692.83 725.81 2777.31 2947.21 1696.07 1332.75 2248.29 1540.76 3641.56 776.28 0.00 1253.74 1953.81 1199.71 2517.67 1496.87
[/cpp]

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
what is the maximum number of vertex possible ? At the first, I just set maximumVertex to 10 and unfortunately I didn't get "RTE" from the judge...

can somebody clarify whether my I-O is correct ?

input :
[cpp]
1 0 0
1 0 0
4 37 1 80 19 97 93 20 82
5 66 46 76 93 11 86 18 63 31 53
8 18 1 92 2 96 67 95 79 71 88 21 90 3 87 1 46
9 71 6 92 27 98 37 96 70 92 96 82 96 13 86 11 84 1 25
10 34 3 67 3 81 7 99 50 92 64 70 95 52 99 11 93 3 76 4 6
10 86 1 97 10 89 61 71 89 37 98 4 92 1 63 1 45 25 11 68 2
10 67 1 74 1 90 3 96 52 99 82 73 92 12 83 9 81 2 14 41 2
11 41 3 91 8 98 9 99 29 98 85 93 88 67 95 26 95 1 85 4 28 5 15
1 42 73
1 22 29
11 51 1 65 4 93 21 99 69 99 73 96 95 42 98 10 95 6 71 3 39 6 10
9 61 4 98 23 99 69 99 73 77 90 8 91 3 42 1 17 30 5
7 41 9 98 19 96 84 59 96 25 90 20 52 18 33
6 76 2 79 66 70 94 53 88 8 46 2 13
7 11 1 94 1 95 23 94 72 38 96 13 92 12 78
10 16 1 80 1 97 4 99 22 98 43 95 86 17 98 11 96 2 34 2 5
10 17 2 75 3 86 7 94 11 98 19 95 90 84 95 37 83 2 72 4 9
11 79 4 89 14 96 35 96 52 86 78 74 95 66 94 4 86 5 40 6 24 64 6
9 40 2 82 2 97 59 99 93 32 98 15 98 6 62 4 24 10 18
9 57 3 86 22 96 51 88 93 11 89 1 40 3 27 9 16 40 5
8 60 1 98 56 95 75 67 98 55 97 9 93 2 79 9 7
10 45 4 72 7 93 10 99 42 98 80 96 90 88 94 57 97 14 81 27 11
8 80 2 87 12 99 37 96 99 6 88 2 59 5 42 13 6
7 61 1 79 30 95 91 70 95 34 98 7 99 3 4
9 31 1 99 9 96 62 87 95 38 94 13 91 3 57 6 47 23 2
10 36 2 88 2 99 20 94 38 78 90 35 99 8 81 2 73 7 22 23 9
9 68 2 90 18 93 30 97 78 91 87 76 95 17 98 1 95 3 19
8 41 6 94 6 92 82 82 96 47 98 23 95 3 85 1 10
14 68 1 69 1 99 29 94 65 91 76 81 96 24 99 21 98 3 83 1 68 3 52 15 30 15 30 19 15
12 79 3 92 11 93 12 94 20 84 68 68 88 59 99 42 97 29 95 1 74 1 47 22 12
7 68 6 99 17 88 65 49 95 4 83 21 40 35 7
5 92 1 67 84 64 91 12 91 2 5
9 84 12 91 20 93 69 93 89 83 92 38 94 14 94 5 36 59 17
8 26 5 69 28 98 63 99 68 84 86 16 86 13 72 13 36
4 42 17 67 33 7 88 12 51
6 5 12 81 13 99 28 67 92 17 83 5 25
12 12 1 17 1 33 2 80 7 90 34 96 68 91 91 70 99 12 87 1 66 1 50 8 17
10 37 1 57 4 84 15 97 34 97 97 15 89 11 82 1 58 2 37 11 16
0
[/cpp]

output :
[cpp]
0.00 0.00 5163.54 6493.36 8861.36 0.00 8430.79 6369.57 7132.16 7797.12 6214.19 0.00 7147.38 2620.81 4493.32 2755.21 6168.21 7399.86 0.00 2884.10
[/cpp]

thank you for your attention