### cross-product result may exceeds INT range

Posted:

**Sun Feb 15, 2004 11:33 am** Replace 'int' by 'double' or 'long long int' in cross-product function

Page **3** of **4**

Posted: **Sun Feb 15, 2004 11:33 am**

Replace 'int' by 'double' or 'long long int' in cross-product function

Posted: **Sun Mar 07, 2004 10:20 pm**

The algorithm consists of three parts.

Lets take vertix 1, where 1 is the vertix with minimal y coorinate.

Sort all the verticies by value of arctan(tha angle bitween the line connecting verticies i and 1 and x axis).

So we will find the convex hull.

Divide the polygon ito n - 2 triangles.

Put points in the centres of that triangles with eight equal to the sqare of that triangle.

Find the centre of n - 2 points.

That's all.

Lets take vertix 1, where 1 is the vertix with minimal y coorinate.

Sort all the verticies by value of arctan(tha angle bitween the line connecting verticies i and 1 and x axis).

So we will find the convex hull.

Divide the polygon ito n - 2 triangles.

Put points in the centres of that triangles with eight equal to the sqare of that triangle.

Find the centre of n - 2 points.

That's all.

Posted: **Wed Apr 07, 2004 6:58 am**

Try this data

Input :

4

19999999999 1

1 3

3 1

1 2

1

Output :

6666666667.333 1.667

Input :

4

19999999999 1

1 3

3 1

1 2

1

Output :

6666666667.333 1.667

Posted: **Thu Aug 05, 2004 3:58 pm**

I use formula below,why WA?Thanks in advance!

Posted: **Thu Aug 05, 2004 4:00 pm**

Posted: **Fri Aug 27, 2004 5:46 pm**

HELP ....

I get WA! my cases (i wanna + cases in AC program plix)

4

1 1

1 3

3 1

1 2

4

19999999999 1

1 3

3 1

1 2

out put

1.667 1.667

6666666667.333 1.667

I get WA! my cases (i wanna + cases in AC program plix)

4

1 1

1 3

3 1

1 2

4

19999999999 1

1 3

3 1

1 2

out put

1.667 1.667

6666666667.333 1.667

Posted: **Sat Aug 28, 2004 6:13 am**

i find my problem try

4

1 1

-1 -1

-1 1

1 -1

see if your answer is

-0.000 -0.000 // no good

good lock.

Posted: **Sun Nov 14, 2004 11:50 am**

Hi!

Could anybody explian me how to sort these points? Is there any efficent algo for that?

Could anybody explian me how to sort these points? Is there any efficent algo for that?

Posted: **Sun Jan 16, 2005 11:33 pm**

Isn't the center of masses simply the point

(Cx,Cy) where

Cx = ( Sum ( x* , i = 0,1,..,N ) ) DIV N;*

Cy = ( Sum ( y* , i = 0,1,..,N ) ) DIV N;*

By DIV I mean normal division floating point division.

That was my impression for center of masses.

What are the formulas you are giving above?

Can you point me to some source which defines the

"term" center of masses differently that I do.

What is strange is that for the test case:

7

-4 -4

-6 -3

-4 -10

-7 -12

-9 -8

-3 -6

-8 -3

I get answer:

-5.857 -6.571

which is far away from

-6.102 -7.089

and that is the answer shown on the problem page:

http://acm.uva.es/p/v100/10002.html

(Cx,Cy) where

Cx = ( Sum ( x

Cy = ( Sum ( y

By DIV I mean normal division floating point division.

That was my impression for center of masses.

What are the formulas you are giving above?

Can you point me to some source which defines the

"term" center of masses differently that I do.

What is strange is that for the test case:

7

-4 -4

-6 -3

-4 -10

-7 -12

-9 -8

-3 -6

-8 -3

I get answer:

-5.857 -6.571

which is far away from

-6.102 -7.089

and that is the answer shown on the problem page:

http://acm.uva.es/p/v100/10002.html

Posted: **Sun Jan 16, 2005 11:36 pm**

By the way even using your formulas I can not

get the answer that the author of the problem has given

for the test case:

7

-4 -4

-6 -3

-4 -10

-7 -12

-9 -8

-3 -6

-8 -3

Obviously

1) either the author of the problem has a different idea about

center of masses

OR

2) there is some small mistake in your formulas.

What do you think ?

If someone has managed to solve the problem let's just

give us the right formulas for

Cx and Cy.

get the answer that the author of the problem has given

for the test case:

7

-4 -4

-6 -3

-4 -10

-7 -12

-9 -8

-3 -6

-8 -3

Obviously

1) either the author of the problem has a different idea about

center of masses

OR

2) there is some small mistake in your formulas.

What do you think ?

If someone has managed to solve the problem let's just

give us the right formulas for

Cx and Cy.

Posted: **Mon Feb 07, 2005 4:33 am**

check the old posts and it should give you an idea.

Just do a search on the forum for "10002"

Also, seems like that there is collinear points and floating points in the input, which contradicts the problem specification, but it is true.

Just do a search on the forum for "10002"

Also, seems like that there is collinear points and floating points in the input, which contradicts the problem specification, but it is true.

Posted: **Mon Feb 07, 2005 11:11 am**

"check the old posts and it should give you an idea"

Should give me an idea about what ? About the correct formulas

for Cx and Cy or ... ? Well, I think I've been looking in all threads

in the forum dedicated to problem 10002 and the above

given formulas are the only thing I've found.

Just give me some links pls if it is not much trouble for you.

Apart from this THANKS for the remark that the input can contain

also floating point numbers, that is precious.

Thank you.

Should give me an idea about what ? About the correct formulas

for Cx and Cy or ... ? Well, I think I've been looking in all threads

in the forum dedicated to problem 10002 and the above

given formulas are the only thing I've found.

Just give me some links pls if it is not much trouble for you.

Apart from this THANKS for the remark that the input can contain

also floating point numbers, that is precious.

Thank you.

Posted: **Mon Feb 07, 2005 1:52 pm**

10153EN wrote:I think your definition of centre of mass is not correct for all case, just correct for triangles.

I sure think that these posts give enough hints... If you don't understand the concept why don't you just keep away from this problem?Maarten wrote:Btw, the definition of "Center of mass" is quite easy: Suppose you make the polygon out of wood (make it massive), and try to balance it on the tip of your finger. The center of mass is the single point where it will not fall off your finger.

I think many people here are confused with the center of mass of a number of mass points. If you apply the formulas mentioned above, what you are really calculating is the center of mass in the case that all mass of the polygon is concentrated around the vertices (with each vertex having equal mass). However, in this problem the mass is distributed equally on the polygon.

If you still want to apply the "simple formula" for the center of mass, you can consider the massive polygon as a large number of mass points distributed equally on the polygon. But to get the correct answer, you will have to take the limit in which the number of points goes to infinity, and then your sum becomes an integral.

Posted: **Mon Feb 07, 2005 7:05 pm**

Sedefcho,

I dont mean this threat, hahaha

There's another threat with 2 pages of reply, and the first post of that threat pretty much give you the code for the calculation.

In fact,

http://online-judge.uva.es/board/viewto ... ight=10002

is what I was refering to.

I dont mean this threat, hahaha

There's another threat with 2 pages of reply, and the first post of that threat pretty much give you the code for the calculation.

In fact,

http://online-judge.uva.es/board/viewto ... ight=10002

is what I was refering to.

Posted: **Mon Feb 07, 2005 8:42 pm**

OK, thank you.

I will have a look at that link

when I have some more time.

THREAD by the way, not THREAT

THREAT means something else as you know, I guess.

I will have a look at that link

when I have some more time.

THREAD by the way, not THREAT

THREAT means something else as you know, I guess.