137 - Polygons

[FlyDeath]

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]

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]

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]

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]

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]

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

[Per]

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]

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 ?

please explain me...

[junbin]

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]

Thank you junbin, for your explanation...

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

[junbin]

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]

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]

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]

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]

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