132 - Bumpy Objects

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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: 8)
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

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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

Yes, I solve this question by finding convex hull first

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

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
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am

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
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

132 - Bumpy Objects WA

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

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

Post Reply

Return to “Volume 1 (100-199)”