Description

One company develops a CAD system for crankshaft design. The crankshafts in question are combined of 0 < N <= 100 metal plates. All plates are made of the same alloy and have equal (small) thickness. Each plate has the shape of a polygon with 3 <= Vi <= 200 vertices. All plates in the crankshaft are parallel and firmly connected to each other. They are the only elements of the crankshaft.

Among other features, this CAD system should have a routine for determining the rotation axis of the crankshaft. More precisely, customers sometimes need to find a line, perpendicular to the plane of the crankshaft plates, rotation around which causes minimal vibration of the crankshaft. It is well known that such axis must pass through the mass center of the crankshaft.

The crankshaft design is stored as a set of vertex coordinates for each plate in some Cartesian coordinate system. The plane OXY of the system is parallel to the plates surfaces. All the coordinates are integer, -104 <= Xij , Yij <= 104 , where 1 <= j <= Vi , 1 <= i <= N . The vertices are numbered clockwise (OX axis is directed rightwards, OY axis is directed upwards).

Your program should print the rotation axis coordinates (XR and YR ). The correct answer should be given even for a partially designed crankshaft (consisting of two or more non-connected parts). You should suppose that these parts are firmly connected.

Input

The input file consists of integer numbers, delimited by spaces and/or line feeds. The numbers are specified in the following order:

N

V1 X11 Y11 ... X1V1 Y1V1

...

VN XN1 YN1 ... XNVN YNVN

Output

Output The output file should contain two real numbers: XR and YR . These values must be exact to four digits to the right of the decimal point.

输入数据 1

2 4 -1 -1 -1 1 1 1 1 -1 4 -1 -1 -1 0 0 0 0 -1

输出数据 1

-0.1000 -0.1000 Source Northeastern Europe 2003, Northern Subregion

描述

某公司开发了一个用于曲轴设计的CAD系统。所涉及的曲轴由$0 < N <= 100$个金属板组成。所有板材由相同合金制成，且厚度相同（厚度较小）。每个板材的形状是一个多边形，顶点数为$3 <= Vi <= 200$。曲轴中的所有板材彼此平行且牢固连接。它们是曲轴的唯一组成部分。

该CAD系统的功能之一是需要一个确定曲轴旋转轴线的例程。更准确地说，客户有时需要找到一条与曲轴板材平面垂直的直线，使得绕该直线旋转时曲轴的振动最小。众所周知，这样的轴必须穿过曲轴的质量中心。

曲轴的设计以每组板材顶点坐标的形式存储在某个笛卡尔坐标系中。坐标系的OXY平面与板材表面平行。所有坐标均为整数，范围是$-10^4 <= Xij, Yij <= 10^4$，其中$1 <= j <= Vi，1 <= i <= N$。顶点按顺时针方向编号（OX轴向右，OY轴向上）。

你的程序应输出旋转轴的坐标（XR和YR）。即使对于部分设计的曲轴（由两个或多个非连接部分组成），也应给出正确答案。需假设这些部分已牢固连接。

输入

输入文件由整数组成，以空格和/或换行符分隔。数字按以下顺序排列：

$N$ $V1 X11 Y11 ... X1V1 Y1V1$ ...
$VN XN1 YN1 ... XNVN YNVN$

输出

输出文件应包含两个实数：XR和YR。这些值必须精确到小数点后四位。

示例输入 1

2
4 -1 -1 -1 1 1 1 1 -1
4 -1 -1 -1 0 0 0 0 -1

示例输出 1

-0.1000 -0.1000

来源
Northeastern Europe 2003, Northern Subregion

算法标签

计算几何，多边形质心计算，加权平均

题意分析

题目要求我们找到曲轴的旋转轴，该轴必须垂直于所有板材的平面（即平行于OXY平面的法向量），并且穿过整个曲轴的质量中心（质心）。由于所有板材的材料相同且厚度相同，质心的计算可以简化为所有板材的几何中心的加权平均，权重为每个板材的面积。

解题思路

1. 计算每个多边形的面积和质心：

   • 使用**鞋带公式（Shoelace Formula）**计算每个多边形的面积。
   • 同时利用鞋带公式计算多边形的几何中心（质心）。

2. 计算整个曲轴的质心：

   • 由于所有板材的材料和厚度相同，总质心是所有多边形质心的加权平均，权重为每个多边形的面积。
   • 总质心坐标 ( (X_R, Y_R) ) 的计算公式： [ X_R = \frac{\sum_{i=1}^{N} (A_i \cdot X_i)}{\sum_{i=1}^{N} A_i}, \quad Y_R = \frac{\sum_{i=1}^{N} (A_i \cdot Y_i)}{\sum_{i=1}^{N} A_i} ] 其中 ( A_i ) 是第 ( i ) 个多边形的面积，( (X_i, Y_i) ) 是其质心。

C++代码实现

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

// 计算多边形的面积和质心
pair<double, Point> computePolygonCentroid(const vector<Point>& polygon) {
    double area = 0;
    Point centroid(0, 0);
    int n = polygon.size();
    
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        double cross = polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
        area += cross;
        centroid.x += (polygon[i].x + polygon[j].x) * cross;
        centroid.y += (polygon[i].y + polygon[j].y) * cross;
    }
    
    area /= 2.0;
    double factor = 1.0 / (6.0 * area);
    centroid.x *= factor;
    centroid.y *= factor;
    
    return {abs(area), centroid}; // 面积取绝对值（鞋带公式可能为负）
}

int main() {
    int N;
    cin >> N;
    
    double totalArea = 0;
    Point totalCentroid(0, 0);
    
    for (int i = 0; i < N; ++i) {
        int V;
        cin >> V;
        vector<Point> polygon(V);
        
        for (int j = 0; j < V; ++j) {
            cin >> polygon[j].x >> polygon[j].y;
        }
        
        auto [area, centroid] = computePolygonCentroid(polygon);
        totalArea += area;
        totalCentroid.x += area * centroid.x;
        totalCentroid.y += area * centroid.y;
    }
    
    totalCentroid.x /= totalArea;
    totalCentroid.y /= totalArea;
    
    cout << fixed << setprecision(4);
    cout << totalCentroid.x << " " << totalCentroid.y << endl;
    
    return 0;
}