132 - Bumpy Objects

wyvmak · Post by **wyvmak** » Thu Jan 03, 2002 2:19 pm

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.

.. · Post by .. » Fri Jan 04, 2002 1:22 pm

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 · Post by **wyvmak** » Sun Jan 20, 2002 12:27 pm

so is this problem requires something like Convex Hull? you're seemingly to hint that

.. · Post by .. » Sun Jan 20, 2002 1:23 pm

Yes, I solve this question by finding convex hull first

Max Fate · Post by **Max Fate** » Fri Mar 15, 2002 9:05 pm

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 · Post by **Stefan Pochmann** » Fri Mar 15, 2002 10:33 pm

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 · Post by **Max Fate** » Sun Mar 17, 2002 10:44 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 · Post by **FlyDeath** » Tue Mar 26, 2002 6:19 am

Well,at least you get PE.I get WA and I don't even know why.Is there any special test case?

wyvmak · Post by **wyvmak** » Tue Mar 26, 2002 6:26 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 · Post by **Maarten** » Thu Oct 02, 2003 12:13 am

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 · Post by **Maarten** » Mon Oct 06, 2003 8:26 pm

Come on people, someone must be able to help me !! Is there noone who can explain me this problem ?

Per · Post by **Per** » Mon Oct 13, 2003 6:14 pm

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 · Post by **Maarten** » Mon Oct 13, 2003 11:11 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 · Post by **Per** » Tue Oct 14, 2003 12:39 am

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

Answer is 6.

Maarten · Post by **Maarten** » Tue Oct 14, 2003 9:38 am

thanks! i think i know what is wrong with my code:

A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.

I didn't notice the word "TOUCHED"....

OJ Board

132 - Bumpy Objects

132 - Bumpy Objects WA