acm-2008-D-Blast the Enemy!

Problem D: Blast the Enemy!

A new computer game has just arrived and as an active and always-in-the-scene player, you should finish it before the
next university term starts. At each stage of this game, you have to shoot an enemy robot on its weakness point. The
weakness point of a robot is always the “center of mass” of its 2D shape in the screen. Fortunately, all robot shapes are
simple polygons with uniform density and you can write programs to calculate exactly the center of mass for each
polygon.

Let’s have a more formal definition for center of mass (COM). The center of mass for a square, (also circle, and other
symmetric shapes) is its center point. And, if a simple shape C is partitioned into two simple shapes A and B with areas
S_A and S_B, then COM(C) (as a vector) can be calculated by

As a more formal definition, for a simple shape A with area S_A:

Input (Standard Input)

The input contains a number of robot definitions. Each robot definition starts with a line containing n, the number of
vertices in robot’s polygon (n <= 100). The polygon vertices are specified in the next n lines (in either clockwise or
counter-clock-wise order). Each of these lines contains two space-separated integers showing the coordinates of the
corresponding vertex. The absolute value of the coordinates does not exceed 100. The case of n=0 shows the end of
input and should not be processed.

Output (Standard Output)

The i^th line of the output should be of the form “Stage #i: x y” (omit the quotes), where (x,y) is the center of mass
for the i^th robot in the input. The coordinates must be rounded to exactly 6 digits after the decimal point.

Sample Input and Output

سوال ت) انفجار دشمن !

یک بازی کامپیوتری جدید منتشر شده است و بازیکن هایی که باید همیشه در صحنه باشند را نیاز دارد. شما باید این بازی را قبل از شروع ترم جدید دانشگاه به پایان برسانید. در هر مرحله از این بازی، شما باید به نقطه ضعف ربات های دشمن شلیک کنید. نقطه ضعف ربات ها همیشه وسط آنها در صفحه نمایش دو بعدی هست. خوشبختانه، تمام شکل های ربات ها چند ضلعی های ساده با تراکم یکنواخت می باشد. شما باید برنامه ای بنویسید که درست وسط هر یک از این چند ضلعی ها را محاسبه کند.

بیاید تعریف متعارف برای پیدا کردن مرکز جرم (COM) ارائه بدهیم. مرکز جرم مثلث یا دایره یا هر شکل متقارنی، در وسط آن هست. اگر یک شکل ساده C به دو قسمت با اشکال ساده A و B تقسیم شود که محدوده S_A و S_B باشد، سپس COM(C) به صورت زیر محاسبه می شود:

به عنوان یک تعریف متعارف، برای شکل ساده A با محدوده S_A:

ورودی

ورودی شامل تعدادی تعریف از ربات ها می باشد. هر تعریف ربات با یک خط شامل n شروع می شود، که بردار مختصات هر یک از ربات ها را نشان می دهد n<=100. بردارهای چند ضلعی با n خط بعدی مشخص شده اند که می تواند ساعت گرد یا پاد ساعت گرد باشند. هر یک از این خطوط شامل ۲ عدد صحیح می باشند که مختصات بردارها را نمایش می دهد. مقدار این مختصات ها نباید بیشتر از 100 باشد. مورد n=0 یعنی به پایان ورودی رسیده ایم و نباید پردازش دیگری انجام شود.

خروجی

هر خط از خروجی باید به شکل “Stage #i: x y” باشد که (x,y) مرکز جرم هر ربات در ورودی است. نتیجه باید تا 6 رقم اعشار رند شود.

ورودی و خروجی ساده