11177 - Fighting Against a Polygonal Monster

rio · Post by **rio** » Mon Feb 26, 2007 4:43 pm

Getting many WA..
Could someone verify my I/O test ?
Input:

6 0.34
-1.2  -1.0
-3.45 0.8
1.34  5.3
5.31  2.11
5.31  -1.0
4.74  -2.0
6 13.42
4.74  -2.0
5.31  -1.0
5.31  2.11
1.34  5.3
-3.45 0.8
-1.2  -1.0
6 27.77
4.74  -2.0
5.31  -1.0
5.31  2.11
1.34  5.3
-3.45 0.8
-1.2  -1.0
6 39.12
4.74  -2.0
5.31  -1.0
5.31  2.11
1.34  5.3
-3.45 0.8
-1.2  -1.0
4 320.00
10 10
10 -10
-10 -10
-10 10
4 356.2
10 10
10 -10
-10 -10
-10 10
4 390.00
10 10
10 -10
-10 -10
-10 10
0

Output:

Code: Select all

Case 1: 0.33
Case 2: 2.33
Case 3: 3.93
Case 4: 5.43
Case 5: 10.11
Case 6: 11.02
Case 7: 12.60

Thanks in advance.

rio · Post by **rio** » Mon Feb 26, 2007 6:44 pm

Oops, silly bug. Got AC.

little joey · Post by **little joey** » Fri May 04, 2007 10:32 am

I'm also getting lots of WAs. I'm getting the same values as listed above (which I assume are correct). What was your silly bug?

rio · Post by **rio** » Fri May 04, 2007 8:58 pm

I don't remember it exactly, but I'm sure that it was realy silly (like "array size was small" ..), not about the logic.

little joey · Post by **little joey** » Sat May 05, 2007 8:02 am

I got accepted. Must have been a rounding error, because now I print the upper value of the binary search in stead of the lower value.

nafi · Post by **nafi** » Wed May 16, 2007 9:21 pm

Output for the 4th input case is wrong. At first, I was also getting 5.43, and, of course, WA in UVA Judge. Later, I found a logical error in my code. The correct answer for that case is 5.38.

Shahriar Rouf Nafi

little joey · Post by **little joey** » Wed May 16, 2007 9:33 pm

Hmm. I'm not going to calculate it by hand, but my AC solution gives 5.43.

In fact, my program calculates the following list of radius/area:

Code: Select all

5.300000 38.754044
5.310000 38.800416
5.320000 38.841574
5.330000 38.878272
5.340000 38.911775
5.350000 38.942542
5.360000 38.970842
5.370000 38.996858
5.380000 39.020728
5.390000 39.042560
5.400000 39.062442
5.410000 39.080629
5.420000 39.097759
5.430000 39.113905
5.440000 39.129093
5.450000 39.143345
5.460000 39.156680
5.470000 39.169131
5.480000 39.180917
5.490000 39.192116
5.500000 39.202741

which would indicate that 5.43 is indeed the correct value, not 5.38.

nafi · Post by **nafi** » Wed May 16, 2007 11:08 pm

I am sorry. Yes, the correct answer is 5.43. I had errors with floating point comparison in my previous AC code. Thanks to Little Joey for helping me finding my mistake. Now, my AC code gives 5.43. However, I don't know how my previous code got AC.

Sorry again for the confusion.

rujialiu · Post by **rujialiu** » Sat May 26, 2007 7:03 am

nafi wrote:I am sorry. Yes, the correct answer is 5.43. I had errors with floating point comparison in my previous AC code. Thanks to Little Joey for helping me finding my mistake. Now, my AC code gives 5.43. However, I don't know how my previous code got AC.

Sorry again for the confusion.

I admit, the test cases are not carefully designed.... sorry

windows2k · Post by **windows2k** » Sat Jun 02, 2007 2:21 pm

rujialiu wrote:
nafi wrote:I am sorry. Yes, the correct answer is 5.43. I had errors with floating point comparison in my previous AC code. Thanks to Little Joey for helping me finding my mistake. Now, my AC code gives 5.43. However, I don't know how my previous code got AC.

Sorry again for the confusion.
I admit, the test cases are not carefully designed.... sorry

Does someone give me some hints to solve the problem?
First, I spilt the polygon into several triangles.
Then, i want to calculate the area the circle intesect the triangles, but I don't know how to handle it.
Or betterr method exist?
Thx in advance

rujialiu · Post by **rujialiu** » Sun Jun 03, 2007 4:55 pm

windows2k wrote: Does someone give me some hints to solve the problem?
First, I spilt the polygon into several triangles.
Then, i want to calculate the area the circle intesect the triangles, but I don't know how to handle it.
Or betterr method exist?
Thx in advance

I don't know how other people solve it, the judge solution does exactly the same as you said. Actually you're intersecting each triangle with a sector.

Suppose the triangle is OAB, the sector is OA'B', where OAA' are on one line, OBB' on another line. Discuss the relationships between OAA' and OBB'. Attention to the case when A' is inside OA and B' is inside OB. That does not mean the sector is completely inside the triangle. (computing the intersection of AB and A'B' first is a good idea) The sector perimeter might go out of the triangle for some while, and come into it again

Be patient, you can finish it

windows2k · Post by **windows2k** » Sun Jun 17, 2007 3:57 am

I have passed the input and output in the board.
But I still get WA. I thought it is a rounding problem.
Could someone give me some tricky input and output?
Thanks in advance.

windows2k · Post by **windows2k** » Thu Jul 12, 2007 5:54 pm

windows2k wrote:I have passed the input and output in the board.
But I still get WA. I thought it is a rounding problem.
Could someone give me some tricky input and output?
Thanks in advance.

Could someone give the output for these input?

Code: Select all

5 4362.18
-94.26 11.90
-36.45 -50.16
-6.41 -101.80
50.64 -63.22
92.33 -17.62
7 5851.67
102.98 46.50
61.49 93.61
-8.64 35.97
-47.22 -92.67
-23.38 -91.05
5.55 -117.87
70.84 -94.37
9 5023.00
67.80 56.09
37.57 68.35
-2.69 56.93
-55.20 25.97
-66.54 30.04
-6.89 -43.46
4.01 -31.75
20.66 -57.40
64.96 -2.05
5 1543.47
11.34 -65.02
18.20 -66.56
31.84 -88.45
25.07 -18.23
111.77 -7.04
3 2459.99
3.70 117.94
-45.10 49.55
-3.14 -39.88
3 2436.19
-79.93 39.15
-40.31 -40.31
18.75 -29.56
7 4249.42
-82.84 75.37
-46.17 -8.81
-9.56 -50.10
-9.55 -60.25
-8.32 -58.42
64.24 -85.57
55.06 -23.83
9 19152.15
106.09 32.63
36.93 85.35
-23.73 114.56
-13.62 26.73
-30.36 55.20
-92.08 -13.11
-78.37 -58.85
31.74 -92.72
90.32 -32.52
9 10029.75
79.36 10.02
19.44 51.44
-46.07 106.45
-72.70 56.38
-102.99 46.50
21.99 -44.91
24.73 -36.40
93.58 -16.34
34.56 -5.48
4 18400.38
50.36 12.93
-1.80 56.97
-94.65 52.02
18.39 -105.41
0

Thanks in advance

Darko · Post by **Darko** » Tue Jul 17, 2007 11:13 pm

I get this:

Code: Select all

Case 1: 37.26
Case 2: 51.06
Case 3: 41.44
Case 4: 22.17
Case 5: 29.65
Case 6: 27.85
Case 7: 45.44
Case 8: 82.13
Case 9: 81.51
Case 10: 227.88

windows2k · Post by **windows2k** » Thu Jul 19, 2007 1:48 am

Sorry for my mistake. I generate inproper data.
And the output should be useless.
Could you give the output for me?

Code: Select all

7 231.18
12.00 0.00
8.73 10.95
-2.89 12.67
-11.71 5.64
-8.11 -3.90
-2.89 -12.67
8.73 -10.95
7 190.45
9.00 0.00
4.99 6.25
-3.12 13.65
-12.61 6.07
-7.21 -3.47
-2.23 -9.75
5.61 -7.04
6 132.65
6.00 0.00
3.50 6.06
-4.00 6.93
-10.00 0.00
-2.50 -4.33
6.50 -11.26
3 101.42
7.00 0.00
-6.00 10.39
-4.50 -7.79
4 110.50
7.00 0.00
0.00 13.00
-14.00 0.00
-0.00 -8.00
5 97.82
6.00 0.00
4.33 13.31
-8.09 5.88
-6.47 -4.70
2.47 -7.61
4 121.50
11.00 0.00
0.00 14.00
-12.00 0.00
-0.00 -7.00
7 93.93
11.00 0.00
4.99 6.25
-1.78 7.80
-9.91 4.77
-6.31 -3.04
-2.89 -12.67
5.61 -7.04
8 267.99
6.00 0.00
8.49 8.49
0.00 10.00
-5.66 5.66
-11.00 0.00
-8.49 -8.49
-0.00 -7.00
9.90 -9.90
8 49.10
11.00 0.00
4.95 4.95
0.00 6.00
-3.54 3.54
-12.00 0.00
-4.95 -4.95
-0.00 -7.00
4.24 -4.24