11460  Balance
Moderator: Board moderators
11460  Balance
do i have to implement centroid of a polygon algorithm from formula like in http://en.wikipedia.org/wiki/Centroid
or is there a simple way that i couldnt figure it out yet ...any idea?
or is there a simple way that i couldnt figure it out yet ...any idea?
Re: 11460  Balance
i figured out as:
first make two polygon set as above and below the xaxis.
second add the points to these polygons at which points original big polygon crosses the xaxis.
third find the centroids of these polygons.
finally find the diff. between x coordinates of two centroids.
the important step is second step. when you adding this points to the polygons you have to be careful about the order of the points.
all i need now is to express this as a code.
first make two polygon set as above and below the xaxis.
second add the points to these polygons at which points original big polygon crosses the xaxis.
third find the centroids of these polygons.
finally find the diff. between x coordinates of two centroids.
the important step is second step. when you adding this points to the polygons you have to be careful about the order of the points.
all i need now is to express this as a code.

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 11460  Balance
Well in test case given in the problem
first polygon>(0 1) (2 3) (4 1) ..Its centroid(2,5/3)
second polygon>(4 3) (2 3) (2 1) (0 1)..Its centroid (2,2)
Hence the difference between the X coordinate is 0.
then how come the answer is 0.5??
Can u plz xplain
first polygon>(0 1) (2 3) (4 1) ..Its centroid(2,5/3)
second polygon>(4 3) (2 3) (2 1) (0 1)..Its centroid (2,2)
Hence the difference between the X coordinate is 0.
then how come the answer is 0.5??
Can u plz xplain
Re: 11460  Balance
as i wrote before since there are two polygon sets we have to add extra points (on wich points the xaxis crossed) to these two polygons.
so the polygons must be:
CE: (0, 0), (0, 1), (2, 3), (4, 1), (4, 0) xcoord of centroid is 2
CLR: (4, 0), (4, 3), (2, 3), (2, 1), (0, 1), (0, 0) xcoord of centroid is 2.5
so the difference is 0.5
so the polygons must be:
CE: (0, 0), (0, 1), (2, 3), (4, 1), (4, 0) xcoord of centroid is 2
CLR: (4, 0), (4, 3), (2, 3), (2, 1), (0, 1), (0, 0) xcoord of centroid is 2.5
so the difference is 0.5

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 11460  Balance
the x coordinate of CLR shud be 2 I think.
How come its 2.5
How come its 2.5
Re: 11460  Balance
in this page:
http://local.wasp.uwa.edu.au/~pbourke/g ... /polyarea/
you can find some sample codes.
according to my calculations test case is correct.
http://local.wasp.uwa.edu.au/~pbourke/g ... /polyarea/
you can find some sample codes.
according to my calculations test case is correct.

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 11460  Balance
Thnx got it.Now i will try 2 solve it
Keep posting..
Keep posting..
11460  Balance
I'm getting wa.
For the below Inputs my code generates following outputs.
Input:
Output:
Can anyone who solved this problem can provide more input/output? I'm not getting any reason for WA.
For the below Inputs my code generates following outputs.
Input:
Code: Select all
15
5
0 3
4 1
3 1
3 1
4 1
5
3 1
3 1
4 1
0 3
4 1
8
0 0
0 1
2 3
4 1
4 3
2 3
2 1
0 1
7
0 1
0 1
2 1
2 3
4 3
4 1
2 3
7
0 1
2 3
4 1
4 3
2 3
2 1
0 1
7
0 1
2 1
2 3
4 3
4 1
2 3
0 1
7
4 3
4 1
2 3
0 1
0 1
2 1
2 3
7
4 3
4 1
2 3
0 1
0 1
2 1
2 3
7
0 1
0 1
2 1
2 3
4 3
4 1
2 3
9
3 0
3 3
0 3
0 0
1 0
2 0
2 3
1 3
1 0
9
3 0
1 0
1 3
2 3
2 0
1 0
0 0
0 3
3 3
10
0 3
300 3
3 0
1 0
1 3
2 3
2 0
4 0
301 3
0 3
3
1 2
4 1
2 1
3
1 2
4 1
2 1
3
1 2
4 1
2 1
Code: Select all
Balanced.
Balanced.
CE is aft of CLR by 0.50 units.
CE is aft of CLR by 0.50 units.
CE is aft of CLR by 0.50 units.
CE is aft of CLR by 0.50 units.
CE is aft of CLR by 0.50 units.
CE is forward of CLR by 0.50 units.
CE is forward of CLR by 0.50 units.
CE is aft of CLR by 2.00 units.
CE is aft of CLR by 2.00 units.
Balanced.
Balanced.
CE is forward of CLR by 2.00 units.
CE is aft of CLR by 2.00 units.
Re: 11460  Balance
Can there be any inputs like below?
The problem description doesn't clarify this...
Input:
The problem description doesn't clarify this...
Input:
Code: Select all
2
5
3 2
0 1
3 2
3 2
3 2
6
3 2
1 0
1 0
3 2
3 2
3 2
Re: 11460  Balance
Problem definition says:
"The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates."
from this i understand:
1. points are in clockwise order or counterclockwise order along the coordinate system. (but when you are solving it must be clockwise order. i dont know why i just saw this in some document about polygon centroids. )
2. x coordinates can be negative. (i dont see any statement about it in the problem.)
according to these your inputs seems correct to me.
but i really wonder the judge's test case because i get WA too
"The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates."
from this i understand:
1. points are in clockwise order or counterclockwise order along the coordinate system. (but when you are solving it must be clockwise order. i dont know why i just saw this in some document about polygon centroids. )
2. x coordinates can be negative. (i dont see any statement about it in the problem.)
according to these your inputs seems correct to me.
but i really wonder the judge's test case because i get WA too