132 - Bumpy Objects

[lantimilan]

Maniac's output is
Code:

UZJWU 13
YVTJTOOO 20

This is what should be output. Since the first polygon has point 1 point 2 and center form a triangle with 90deg, so segment(point 1, point 2) should be rejected as baseline. The same for the second polygon.

Also, about the format, I guess the magic 19 comes from the fact that the name of object is at most 20 char. But why is it not 20?

[LPH]

Maniac's output is
Code:

UZJWU 13
YVTJTOOO 20

This is what should be output. Since the first polygon has point 1 point 2 and center form a triangle with 90deg, so segment(point 1, point 2) should be rejected as baseline. The same for the second polygon.

It's correct to reject those baselines which their endpoints and the center forms triangle with 90 degrees, according to the problem statement:

An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints.

But in the first polygon, point 1, point 2 and the center don't form a triangle with 90 degrees(you can see that in the picture.)

By the way, my program had AC'ed after Maniac's confirmation. (Can we say that's one of the mistakes in ACM? )

Also, about the format, I guess the magic 19 comes from the fact that the name of object is at most 20 char. But why is it not 20?

The problem statement says:

a string of less than 20 characters identifying the object

[xixi]

But in the first polygon, point 1, point 2 and the center don't form a triangle with 90 degrees(you can see that in the picture.)

I think they form a 90 degree, got AC is because the judge haven't such test cases.

I change my code with reject and accept 90 degrees both get AC

[LPH]

But in the first polygon, point 1, point 2 and the center don't form a triangle with 90 degrees(you can see that in the picture.)

I think they form a 90 degree, got AC is because the judge haven't such test cases.

I change my code with reject and accept 90 degrees both get AC

You are correct. They do form a triangle with 90 degrees. Simply calculate the distance between them will prove it. And the reason why in the picture it seems not is the aspect of the picture...(The default aspect of X axis and Y axis in Mathematica is about 1.618 to 1 )
But my program didn't get a rejudge after I AC....

[wfuny]

this article is write by Erik
Well, after trying some new things again I finally got AC for this problem. Here are some things I found out which might be usefull:

- Input coordinates are all integers (so this problem is solvable in an exact way, no doubles required)
- Input coordinates are all non-negative
- Object names do not contain whitespace and aren't numbers
- maximum number of points per object is surely less than 100000
- Input contains objects where the given 'center of mass' really isn't the physical center of mass of the object
- Input does not contain objects where the center of mass is completely outside the convex hull of the object
- Input however does contain objects where the center of mass is ON the convex hull (and the object need not be made of only colinear points)
- For every input object there is at least one acceptable base line
- The baseline with minimal number, has a number greater than zero and smaller than 100

But these are all little things that shouldn't give too much problems. However (and this turned my WA into AC), the sentence

'when this line is horizontal, the centre of mass lies ... strictly between its endpoints'

should be interpreted as

- when this line is horizontal, the center of mass lies between its endpoints or precisely above one of its endpoints

I don't know about you guys, but in my opinion STRICTLY BETWEEN means really between, so endpoints excluded. This also makes more sense for the object to be able to stand stably....

Ow, and in order to get AC instead of PE the result of each object should be:

[NAMEJUSTIFIED][SPACE][NRJUSTIFIED][ENDOFLINE]

where NAMEJUSTIFIED must have length 19 and is left justified
and NRJUSTIFIED must have length 2 and is right justified
(this means that the sample outputs are wrong!)

for example:

Code:
Object2 6
SquareWithALongName 27
..........................................................................................
I think the most important thing is that .....................................

'when this line is horizontal, the centre of mass lies ... strictly between its endpoints'

should be interpreted as

- when this line is horizontal, the center of mass lies between its endpoints or precisely above one of its endpoints

where NAMEJUSTIFIED must have length 19 and is left justified
and NRJUSTIFIED must have length 2 and is right justified
(this means that the sample outputs are wrong!)

printf("%-19s %2d\n", names, minNum);

and if 'center of mass' On the edge , this is not the stable positions......

if you notice things above , i think you can get AC

[wfuny]

and such case doesn't exist

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

so you don't have to judge again

[Moha]

WoW I had gotten this problem years ago, but I was noticed that my AC had changed into WA. I just change my output formating and I got it again.
I think judge still has so many problem with PE which made itself to consider some PE as WA.

[Joth]

i am curious how did you determine the center of mass might not really be the true center of mass? i think you are right, but the only way i can think of determining that is to calculate the center of mass and if it is incorrect, put the routine into a loop and check for a timeout by the judge.

[rafastv]

Just some tips for you:

1) The center of mass is not always inside the object nor even the convex hull.

2) It really does help plotting all problems that deal with geometry using maybe an on-line tool (or some library)
https://www.math10.com/en/geometry/geog ... gebra.html