137 - Polygons

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

Moderator: Board moderators

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

Post by junbin » Wed Dec 17, 2003 12:06 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

Post by junbin » Wed Dec 17, 2003 12:09 pm

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed Dec 17, 2003 2:57 pm

I finally got AC with satisfying run time ...

many thanks to junbin ... ( I really have done a silly mistake )

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

Post by junbin » Thu Dec 18, 2003 3:18 pm

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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Thu Dec 18, 2003 4:13 pm

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

great thanks to you, junbin ...

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Sat Feb 07, 2004 1:56 am

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
New poster
Posts: 1
Joined: Tue Jan 13, 2004 6:58 am

137 WA Polygons

Post by sehoon,ha » Wed Feb 18, 2004 6:08 pm

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Feb 19, 2004 3:54 pm

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

geran
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Output from java

Post by geran » Wed Jun 29, 2005 7:18 pm

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?

User avatar
neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

Post by neowarez » Wed Jun 29, 2005 9:54 pm

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

8.2 format using java

Post by Sedefcho » Thu Jun 30, 2005 12:15 pm

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
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Post by geran » Thu Jun 30, 2005 10:13 pm

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

" 5.02" and not
" 0.50"

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu Jun 30, 2005 10:21 pm

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
New poster
Posts: 1
Joined: Fri Aug 24, 2007 5:29 pm

137 WA

Post by lmnop » Fri Aug 24, 2007 6:19 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Aug 24, 2007 7:58 pm

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
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 1 (100-199)”