132  Bumpy Objects
Moderator: Board moderators

 New poster
 Posts: 11
 Joined: Sat Mar 19, 2005 11:12 am
 Location: HKU
 Contact:
The WA output IS correct
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?
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?
 This is Unix, any explanatory error message is seen as a sign of weakness
It's correct to reject those baselines which their endpoints and the center forms triangle with 90 degrees, according to the problem statement:lantimilan wrote: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.
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.)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.
By the way, my program had AC'ed after Maniac's confirmation. (Can we say that's one of the mistakes in ACM? )
The problem statement says:lantimilan wrote: 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?
a string of less than 20 characters identifying the object
LPH [acronym]
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.
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 )xixi wrote:I think they form a 90 degree, got AC is because the judge haven't such test cases.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 change my code with reject and accept 90 degrees both get AC
But my program didn't get a rejudge after I AC....
LPH [acronym]
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.
If you get WA on 132 read this
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 nonnegative
 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
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 nonnegative
 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
and such case doesn't exist
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
...
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
Re: 132  Bumpy Objects
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 online tool (or some library)
https://www.math10.com/en/geometry/geog ... gebra.html
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 online tool (or some library)
https://www.math10.com/en/geometry/geog ... gebra.html