137 - Polygons
Moderator: Board moderators
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.
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.
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.
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.
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
-
- New poster
- Posts: 45
- Joined: Mon Jul 14, 2003 9:42 pm
- Location: Zoetermeer, The Netherlands
Hi Almost human,
Your input is really bad! You don't follow the rules.
1. The polygon has to be convex (not concave).
2. The polygon must be clockwise (not counter-clockwise)
One of the polygons is concave, and all other inputs (bar 2) are counter-clockwise!!!
The 2 correct inputs are:
So, I reversed the polygons:
Your input is really bad! You don't follow the rules.
1. The polygon has to be convex (not concave).
2. The polygon must be clockwise (not counter-clockwise)
One of the polygons is concave, and all other inputs (bar 2) are counter-clockwise!!!
The 2 correct inputs are:
Code: Select all
1 0 0
1 0 0
1 42 73
1 22 29
0
Code: Select all
0.00 0.00
Code: Select all
1 0 0
1 0 0
4 20 82 97 93 80 19 37 1
5 31 53 18 63 11 86 76 93 66 46
8 1 46 3 87 21 90 71 88 95 79 96 67 92 2 18 1
9 1 25 11 84 13 86 82 96 92 96 96 70 98 37 92 27 71 6
10 4 6 3 76 11 93 52 99 70 95 92 64 99 50 81 7 67 3 34 3
10 68 2 25 11 1 45 1 63 4 92 37 98 71 89 89 61 97 10 86 1
10 41 2 2 14 9 81 12 83 73 92 99 82 96 52 90 3 74 1 67 1
11 5 15 4 28 1 85 26 95 67 95 93 88 98 85 99 29 98 9 91 8 41 3
1 42 73
1 22 29
11 6 10 3 39 6 71 10 95 42 98 96 95 99 73 99 69 93 21 65 4 51 1
9 30 5 1 17 3 42 8 91 77 90 99 73 99 69 98 23 61 4
7 18 33 20 52 25 90 59 96 96 84 98 19 41 9
6 2 13 8 46 53 88 70 94 79 66 76 2
7 12 78 13 92 38 96 94 72 95 23 94 1 11 1
10 2 5 2 34 11 96 17 98 95 86 98 43 99 22 97 4 80 1 16 1
10 4 9 2 72 37 83 84 95 95 90 98 19 94 11 86 7 75 3 17 2
11 64 6 6 24 5 40 4 86 66 94 74 95 86 78 96 52 96 35 89 14 79 4
9 10 18 4 24 6 62 15 98 32 98 99 93 97 59 82 2 40 2
9 40 5 9 16 3 27 1 40 11 89 88 93 96 51 86 22 57 3
8 9 7 2 79 9 93 55 97 67 98 95 75 98 56 60 1
10 27 11 14 81 57 97 88 94 96 90 98 80 99 42 93 10 72 7 45 4
8 13 6 5 42 2 59 6 88 96 99 99 37 87 12 80 2
7 3 4 7 99 34 98 70 95 95 91 79 30 61 1
9 23 2 6 47 3 57 13 91 38 94 87 95 96 62 99 9 31 1
10 23 9 7 22 2 73 8 81 35 99 78 90 94 38 99 20 88 2 36 2
9 3 19 1 95 17 98 76 95 91 87 97 78 93 30 90 18 68 2
8 1 10 3 85 23 95 47 98 82 96 92 82 94 6 41 6
7 35 7 21 40 4 83 49 95 88 65 99 17 68 6
5 2 5 12 91 64 91 67 84 92 1
9 59 17 5 36 14 94 38 94 83 92 93 89 93 69 91 20 84 12
8 13 36 13 72 16 86 84 86 99 68 98 63 69 28 26 5
4 12 51 7 88 67 33 42 17
6 5 25 17 83 67 92 99 28 81 13 5 12
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1
0
Code: Select all
0.00 3350.18 1866.41 1458.18 1272.38 0.00 1027.32 3092.04 1315.82 1915.00 1129.05 2688.32 201
5.90 1184.53 931.58 2407.83 2095.03 4248.67 881.23
137 WA Polygons
hi.
I solved 137, but still WA.
can somebody give me a testcase??
I use these test case which I found in this board..
1 0 0
1 0 0
4 20 82 97 93 80 19 37 1
5 31 53 18 63 11 86 76 93 66 46
8 1 46 3 87 21 90 71 88 95 79 96 67 92 2 18 1
9 1 25 11 84 13 86 82 96 92 96 96 70 98 37 92 27 71 6
10 4 6 3 76 11 93 52 99 70 95 92 64 99 50 81 7 67 3 34 3
10 68 2 25 11 1 45 1 63 4 92 37 98 71 89 89 61 97 10 86 1
10 41 2 2 14 9 81 12 83 73 92 99 82 96 52 90 3 74 1 67 1
11 5 15 4 28 1 85 26 95 67 95 93 88 98 85 99 29 98 9 91 8 41 3
1 42 73
1 22 29
11 6 10 3 39 6 71 10 95 42 98 96 95 99 73 99 69 93 21 65 4 51 1
9 30 5 1 17 3 42 8 91 77 90 99 73 99 69 98 23 61 4
7 18 33 20 52 25 90 59 96 96 84 98 19 41 9
6 2 13 8 46 53 88 70 94 79 66 76 2
7 12 78 13 92 38 96 94 72 95 23 94 1 11 1
10 2 5 2 34 11 96 17 98 95 86 98 43 99 22 97 4 80 1 16 1
10 4 9 2 72 37 83 84 95 95 90 98 19 94 11 86 7 75 3 17 2
11 64 6 6 24 5 40 4 86 66 94 74 95 86 78 96 52 96 35 89 14 79 4
9 10 18 4 24 6 62 15 98 32 98 99 93 97 59 82 2 40 2
9 40 5 9 16 3 27 1 40 11 89 88 93 96 51 86 22 57 3
8 9 7 2 79 9 93 55 97 67 98 95 75 98 56 60 1
10 27 11 14 81 57 97 88 94 96 90 98 80 99 42 93 10 72 7 45 4
8 13 6 5 42 2 59 6 88 96 99 99 37 87 12 80 2
7 3 4 7 99 34 98 70 95 95 91 79 30 61 1
9 23 2 6 47 3 57 13 91 38 94 87 95 96 62 99 9 31 1
10 23 9 7 22 2 73 8 81 35 99 78 90 94 38 99 20 88 2 36 2
9 3 19 1 95 17 98 76 95 91 87 97 78 93 30 90 18 68 2
8 1 10 3 85 23 95 47 98 82 96 92 82 94 6 41 6
7 35 7 21 40 4 83 49 95 88 65 99 17 68 6
5 2 5 12 91 64 91 67 84 92 1
9 59 17 5 36 14 94 38 94 83 92 93 89 93 69 91 20 84 12
8 13 36 13 72 16 86 84 86 99 68 98 63 69 28 26 5
4 12 51 7 88 67 33 42 17
6 5 25 17 83 67 92 99 28 81 13 5 12
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1
0
and my result :
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 2407.83 2095.03 4248.67 881.23
Press any key to continue
plz send me some testcase or comment..
I solved 137, but still WA.
can somebody give me a testcase??
I use these test case which I found in this board..
1 0 0
1 0 0
4 20 82 97 93 80 19 37 1
5 31 53 18 63 11 86 76 93 66 46
8 1 46 3 87 21 90 71 88 95 79 96 67 92 2 18 1
9 1 25 11 84 13 86 82 96 92 96 96 70 98 37 92 27 71 6
10 4 6 3 76 11 93 52 99 70 95 92 64 99 50 81 7 67 3 34 3
10 68 2 25 11 1 45 1 63 4 92 37 98 71 89 89 61 97 10 86 1
10 41 2 2 14 9 81 12 83 73 92 99 82 96 52 90 3 74 1 67 1
11 5 15 4 28 1 85 26 95 67 95 93 88 98 85 99 29 98 9 91 8 41 3
1 42 73
1 22 29
11 6 10 3 39 6 71 10 95 42 98 96 95 99 73 99 69 93 21 65 4 51 1
9 30 5 1 17 3 42 8 91 77 90 99 73 99 69 98 23 61 4
7 18 33 20 52 25 90 59 96 96 84 98 19 41 9
6 2 13 8 46 53 88 70 94 79 66 76 2
7 12 78 13 92 38 96 94 72 95 23 94 1 11 1
10 2 5 2 34 11 96 17 98 95 86 98 43 99 22 97 4 80 1 16 1
10 4 9 2 72 37 83 84 95 95 90 98 19 94 11 86 7 75 3 17 2
11 64 6 6 24 5 40 4 86 66 94 74 95 86 78 96 52 96 35 89 14 79 4
9 10 18 4 24 6 62 15 98 32 98 99 93 97 59 82 2 40 2
9 40 5 9 16 3 27 1 40 11 89 88 93 96 51 86 22 57 3
8 9 7 2 79 9 93 55 97 67 98 95 75 98 56 60 1
10 27 11 14 81 57 97 88 94 96 90 98 80 99 42 93 10 72 7 45 4
8 13 6 5 42 2 59 6 88 96 99 99 37 87 12 80 2
7 3 4 7 99 34 98 70 95 95 91 79 30 61 1
9 23 2 6 47 3 57 13 91 38 94 87 95 96 62 99 9 31 1
10 23 9 7 22 2 73 8 81 35 99 78 90 94 38 99 20 88 2 36 2
9 3 19 1 95 17 98 76 95 91 87 97 78 93 30 90 18 68 2
8 1 10 3 85 23 95 47 98 82 96 92 82 94 6 41 6
7 35 7 21 40 4 83 49 95 88 65 99 17 68 6
5 2 5 12 91 64 91 67 84 92 1
9 59 17 5 36 14 94 38 94 83 92 93 89 93 69 91 20 84 12
8 13 36 13 72 16 86 84 86 99 68 98 63 69 28 26 5
4 12 51 7 88 67 33 42 17
6 5 25 17 83 67 92 99 28 81 13 5 12
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1
0
and my result :
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 2407.83 2095.03 4248.67 881.23
Press any key to continue
plz send me some testcase or comment..
Output from java
Hi, how should I format the output from my java program to problem 137?
the output should be written with 2 decimals precision and a field width of 8. In C I would do
but how can I get the same result in java?
the output should be written with 2 decimals precision and a field width of 8. In C I would do
Code: Select all
printf("%8.2%f",area)
8.2 format using java
No that's not the only way. Actually what neowarez
suggests won't always work.
Actually in Java you can do this task ( the task of formatting
a double in a 8.2 format ) quite easily.
Hope this helps.
suggests won't always work.
Actually in Java you can do this task ( the task of formatting
a double in a 8.2 format ) quite easily.
Code: Select all
double x = 190234.5678; // the number we want to print in a 8.2 format
long y = (long) ( x * 1000 ); // Note that it is 1000 and not 100
if (y % 10 >= 5) y += 10; // Do rounding !
y /= 10; // Get rid of the last digit !
long z1 = y / 100;
long z2 = y % 100;
String strZ1 = "" + z1;
String strZ2 = "" + z2;
int lenZ1 = strZ1.length();
int lenZ2 = strZ2.length();
for (int k=0; k<8-lenZ1; k++){
strZ1 = " " + strZ1;
}
for (int k=0; k<2-lenZ2; k++){
strZ2 = "0" + strZ2;
}
System.out.println (strZ1 + "." + strZ2);
Well, I don't know what you're doing but apparently you are
making a mistake. The output for the value of x = 0.5025000000000004
becomes:
where s denotes the space character.
I have just tested my code once again
( I use J2SDK version 1.4.2_04 from
Sun Microsystems / JDK 1.4 for short / )
and that's the output produced by my code.
So it is 7 spaces and then 0.50.
And that's what the output should be.
making a mistake. The output for the value of x = 0.5025000000000004
becomes:
Code: Select all
sssssss0.50
I have just tested my code once again
( I use J2SDK version 1.4.2_04 from
Sun Microsystems / JDK 1.4 for short / )
and that's the output produced by my code.
So it is 7 spaces and then 0.50.
And that's what the output should be.
137 WA
Hi,
I can't seem to figure this one out. I implemented it in two different ways and got WA each time. Am I missing any tricky cases, or is my algorithm just wrong?
1. Find area of poly 1 (A1)
2. Find area of poly 2 (A2)
3. Take the convex hull of:
a) points of poly 1 that are in poly 2
b) points of poly 2 that are in poly 1
c) intersection points of poly 1 and poly 2
4. Find area of convex hull (A3)
5. Print A1 + A2 - 2(A3)
I can post code if it will help (it's quite long though).
Thanks for any insight/test cases you can provide!
I can't seem to figure this one out. I implemented it in two different ways and got WA each time. Am I missing any tricky cases, or is my algorithm just wrong?
1. Find area of poly 1 (A1)
2. Find area of poly 2 (A2)
3. Take the convex hull of:
a) points of poly 1 that are in poly 2
b) points of poly 2 that are in poly 1
c) intersection points of poly 1 and poly 2
4. Find area of convex hull (A3)
5. Print A1 + A2 - 2(A3)
I can post code if it will help (it's quite long though).
Thanks for any insight/test cases you can provide!
Search the board first. Dont open a new thread if there is one already. Try the following thread.
http://online-judge.uva.es/board/viewto ... hlight=137
http://online-judge.uva.es/board/viewto ... hlight=137
Ami ekhono shopno dekhi...
HomePage
HomePage