Moderator: Board moderators

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

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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 34  1 2  1 4  5 4  5 26  6 3  8 2  8 1  4 1  4 2  5 35  1 2  1 4  5 4  5 3 4 25  1 2  1 4  5 4  5 3 4 26  6 3  8 2  8 1  4 1  4 2  5 36  6 3  8 2  8 1  4 1  4 2  5 36  1 2  1 4  5 4  5 3 4 3 4 26  1 2  1 4  5 4  5 3 4 3 4 26  6 3  8 2  8 1  4 1  4 2  5 34  0 1  0 2  3 2  3 14  1 0  1 3  2 3  2 04  1 0  1 3  2 3  2 04  0 1  0 2  3 2  3 14  1 0  1 3  2 1  2 04  0 1  0 2  3 2  3 14  0 1  0 2  3 2  3 14  1 0  1 3  2 1  2 00`

Output:
Code: Select all
`   13.50   14.00   14.00   13.50   13.50    4.00    4.00    3.50    3.50`
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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 ?

Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Thank you junbin, for your explanation...

Can you give me more sample input and output ... ? I really need that
Almost Human
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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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]

Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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]

Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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.
junbin
Experienced poster

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

I finally got AC with satisfying run time ...

many thanks to junbin ... ( I really have done a silly mistake )
Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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

Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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

great thanks to you, junbin ...
Almost Human
Learning poster

Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Next