Blast the Enemy!
Time limit1sMemory limit128 MB
Compute and print the centroid of each given simple polygon with six digits after the decimal point.
- Level
Medium4 of 10
- Topics
- Geometry
- Solved
- No attempts yet
Problem
A new computer game just came out, and you want to finish it before the next university term starts. Each stage puts an enemy robot on the screen and you have to hit its weak point. The weak point is always the center of mass of the robot's 2D shape. Every robot shape is a simple polygon with uniform density, so a program can compute that point exactly.
Here is a more formal definition of the center of mass (COM). For a square, a circle, or any other symmetric shape, the center of mass is the center point. If a simple shape is cut into two simple shapes and with areas and , then , taken as a vector, is
More generally, for a simple shape with area ,
Input
The input holds several robot definitions. Each definition starts with a line containing , the number of vertices of the robot's polygon. A robot is a simple polygon, so . The next lines give the vertices in clockwise or counterclockwise order. Each of those lines holds two integers separated by a space, the coordinates of one vertex. The absolute value of a coordinate never exceeds 100. A line with marks the end of the input and is not processed.
Output
For the th robot in the input, print one line of the form Stage #i: x y, where is its center of mass and counts from 1. Round both coordinates to exactly 6 digits after the decimal point. No robot in the input produces a coordinate that lands exactly on a rounding boundary, so the rounded answer is unique.