137 - Polygons

[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 ...

[El-idioto]

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:

Code: Select all

1 0 0
1 0 0
1 42 73
1 22 29
0

Code: Select all

0.00 0.00

So, I reversed the polygons:

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

[sehoon,ha]

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..

[junbin]

If these are the test cases which I provided answers for, then the test cases are faulty... my answers were faulty as well..

[geran]

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

Code: Select all

printf("%8.2%f",area)

but how can I get the same result in java?

[neowarez]

Well.. that is a good question..

That's why I dont use java..

The only way I see now is to pass it to string and .. find the dot.. and you know the rest.

Sorry..

[Sedefcho]

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.

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);
 

Hope this helps.

[geran]

That didnt work, the output for example the x = 0.5025000000000004 becoms

" 5.02" and not
" 0.50"

[Sedefcho]

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:

Code: Select all

sssssss0.50

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.

[lmnop]

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!

[Jan]

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