137 - Polygon - WA - please help

[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

[junbin]

Clarification for my code:

1) Usually when I code, I follow all the assumptions.. so if it says it's a convex hull that is given in a clockwise direction, I'll use that for optimisations... so if the input data is NOT a convex hull or is NOT listed in a clockwise direction, then my code will give the wrong answer.

2) I usually don't allocate extra memory space (at least not a lot).. so if the maximum number of points is say 100, then I'll at most allocate 105.. so if the data set has more, then the overflow may cause an error or wrong answer.

If either of the above doesn't explain the weird behaviour, please tell me. :p


Oh yes.. for this question, I made a quick VB program to visually plot out the points.. that helped me quite a bit.. unfortunately, I've since deleted the VB program. However, if you know any RAD languages such as VB, Delphi, Qb, etc., try to do that.. it'll help.

[junbin]

My program returned these results:

0.00 3350.18 1866.41 1458.18 1272.38 0.00 1027.32 3092.04 1315.82 1915.00 1129.05 2688.32 2015.90 1184.53 931.58 1330.92 2407.83 2095.03 4248.67 881.23



ps, if you give me your email, I can send you the Windows EXE file of my program.. so if you're using a Windows platform (95 and above of course), you can use it to generate data sets.

[Almost Human]

I finally got AC with satisfying run time ...

many thanks to junbin ... ( I really have done a silly mistake )

[junbin]

I assume that means you don't need my EXE anymore...

[Almost Human]

No, you don't need to send it anymore ...

great thanks to you, junbin ...