11177 - Fighting Against a Polygonal Monster

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

11177 - Fighting Against a Polygonal Monster

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

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

Code: Select all

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

Oops, silly bug. Got AC.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

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
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

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 :cry:
:-)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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 :cry:
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
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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

Post Reply

Return to “Volume 111 (11100-11199)”