## 132 - Bumpy Objects

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
can someone explain the question to me? and what is base line? i don't understand how to get from the sample input to the sample output. if 6, where are two vertices it mentioned to not intersect the object.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Object2
4 3
3 2 5 2 6 1 7 1 6 3 4 7 1 1 2 1 0 0

in this example, there are 3 base lines:
vertex6 -> vertex 4 (highest numbered vertex touched: 6)
vertex4 -> vertex 7 (highest numbered vertex touched:
vertex6 -> vertex 7 (highest numbered vertex touched: 7)

So, we should output the lowest numbered base line 6 (vertex6->vertex4)

<font size=-1>[ This Message was edited by: .. on 2002-01-20 12:30 ]</font>

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
so is this problem requires something like Convex Hull? you're seemingly to hint that

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Yes, I solve this question by finding convex hull first

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am
Well, I got PE thus they write
Output will consist of the identification string followed by the number of the relevant base line.

Formatting like sample or putting single space, nothing's got Accepted... Can anyone help me?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Why do you care so much about it? This problem has a simple output format and 2/3 of the solutions are PE and only 1/3 Accepted. It's probably a bug in the description or the judge, so why bothering fixing other people's mistakes?

Believe me, if you care so much about every PE, you'll waste a lot of time. For what?

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am
Well, I don't care too much
but it's a kind of my pedantry.

Better to deal with "Accepted" problems instead of PE, but it isn't the main problem's side

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
Well,at least you get PE.I get WA and I don't even know why.Is there any special test case?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
have you considered "when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints" ? i think it might be the most special sentence in the problem

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

### 132 - Bumpy Objects WA

can someone explain me why the correct answer for the input

Code: Select all

``````WCIOO
39 7
1 44 5 9 9 27 11 22 14 27 17 6 22 1 27 28 29 10 31 6 34 11 39 6 41 12 45 18 49 21 54 3 58 12 60 24 64 7 65 18 65 25 64 20 60 29 58 14 54 22 49 27 45 42 41 14 39 16 34 36 31 26 29 25 27 48 22 10 17 10 14 54 11 45 9 47 5 11 0 0
``````
must be "8", and not 16 as my program says ?

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
Come on people, someone must be able to help me !! Is there noone who can explain me this problem ?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
My AC program answers 16 for that test case.

Why do you think it should be 8?

As I remember, I missed one thing in this problem. I don't remember exactly what, but it occurred in cases where there are several colinear points.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
i found the test input somewhere on the web, together with the output. My program gave 16 which was not the same as the 8 in the output

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
If you found the same ones I found (on a Czechian (I suspect this inflection might be incorrect?) site whose output sadly often suffers this fault) the output's all bogus (easily verified by plotting the polygons and the answers).

This test case checks the thing I did wrong:

Code: Select all

``````...
6 40
1 1 7 1 7 2 5 1 4 2 3 1 1 2 0 0``````