137 - Polygons
Moderator: Board moderators
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!
![:oops:](./images/smilies/icon_redface.gif)
Is there any algorithm that I can use to solve this problem?
Can you give me some tips?
Thanks!
![:oops:](./images/smilies/icon_redface.gif)
![:oops:](./images/smilies/icon_redface.gif)
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:
hth -- Ivan
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
-
- 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
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
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
137 - Polygon - WA - please help
I got WA on this problem. I guess I need more sample input and output. I would be gratefully for any help.
Not sure how meaningful this input is, but it was what I had in my input file. Input:
Output:
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
Code: Select all
13.50 14.00 14.00 13.50 13.50 4.00 4.00 3.50 3.50
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
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.![:)](./images/smilies/icon_smile.gif)
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.
![:)](./images/smilies/icon_smile.gif)
-
- 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
![:(](./images/smilies/icon_frown.gif)
[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
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.
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.
-
- 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]
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]
-
- 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
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