题意分析

题目要求计算两个形状（矩形或圆形）的交集面积，并输出最接近的整数。输入包含多个测试用例，每个用例给出两个形状的参数。形状可以是矩形（R x1 y1 x2 y2）或圆形（C x y r）。

解题思路

1. 形状表示与存储：

   • 矩形：用左上角 (x1, y1) 和右下角 (x2, y2) 表示。
   • 圆形：用圆心 (x, y) 和半径 r 表示。

2. 相交情况分类：

   • 圆与圆相交：计算两圆的交集面积，使用几何公式。
   • 矩形与矩形相交：计算两矩形的交集面积，直接几何计算。
   • 圆与矩形相交：采用蒙特卡洛方法（随机采样）估算交集面积。

3. 蒙特卡洛方法：

   • 将形状放大 200 倍，在网格上遍历所有点。
   • 统计同时属于两个形状的点的数量，乘以单位面积得到交集面积。

4. 几何公式：

   • 圆与圆的交集面积使用余弦定理和扇形面积公式计算。
   • 矩形与矩形的交集面积通过坐标比较计算重叠区域。

标程代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

const double PI = acos(-1.0);

// 计算两点间距离
double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// 计算两圆的交集面积
double circleIntersection(double x1, double y1, double r1, double x2, double y2, double r2) {
    double d = distance(x1, y1, x2, y2);
    if (d >= r1 + r2) return 0;          // 相离
    if (d <= abs(r1 - r2)) {             // 包含
        return PI * min(r1, r2) * min(r1, r2);
    }
    // 相交
    double angle1 = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
    double angle2 = acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d));
    return r1 * r1 * angle1 + r2 * r2 * angle2 - r1 * d * sin(angle1);
}

// 判断点是否在矩形内
bool inRectangle(double x1, double y1, double x2, double y2, double px, double py) {
    return px >= x1 && px <= x2 && py >= y1 && py <= y2;
}

// 判断点是否在圆内
bool inCircle(double cx, double cy, double r, double px, double py) {
    return (px - cx) * (px - cx) + (py - cy) * (py - cy) <= r * r;
}

// 计算矩形与矩形的交集面积
double rectangleIntersection(double x1, double y1, double x2, double y2,
                            double x3, double y3, double x4, double y4) {
    double left = max(x1, x3);
    double right = min(x2, x4);
    double top = max(y1, y3);
    double bottom = min(y2, y4);
    if (left >= right || top >= bottom) return 0;
    return (right - left) * (bottom - top);
}

// 蒙特卡洛方法估算圆与矩形的交集面积
double monteCarloIntersection(double shape1[], bool isRect1,
                             double shape2[], bool isRect2) {
    const int SCALE = 200; // 放大倍数
    const double STEP = 1.0 / SCALE;
    double area = 0;

    // 遍历所有点
    for (double x = 0; x <= 10; x += STEP) {
        for (double y = 0; y <= 10; y += STEP) {
            bool inShape1, inShape2;

            if (isRect1) {
                inShape1 = inRectangle(shape1[0], shape1[1], shape1[2], shape1[3], x, y);
            } else {
                inShape1 = inCircle(shape1[0], shape1[1], shape1[2], x, y);
            }

            if (isRect2) {
                inShape2 = inRectangle(shape2[0], shape2[1], shape2[2], shape2[3], x, y);
            } else {
                inShape2 = inCircle(shape2[0], shape2[1], shape2[2], x, y);
            }

            if (inShape1 && inShape2) {
                area += STEP * STEP;
            }
        }
    }
    return area;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string type1, type2;
        double shape1[4], shape2[4];
        bool isRect1, isRect2;

        cin >> type1;
        isRect1 = (type1 == "R");
        if (isRect1) {
            cin >> shape1[0] >> shape1[1] >> shape1[2] >> shape1[3];
        } else {
            cin >> shape1[0] >> shape1[1] >> shape1[2];
        }

        cin >> type2;
        isRect2 = (type2 == "R");
        if (isRect2) {
            cin >> shape2[0] >> shape2[1] >> shape2[2] >> shape2[3];
        } else {
            cin >> shape2[0] >> shape2[1] >> shape2[2];
        }

        double intersectionArea;
        if (!isRect1 && !isRect2) {
            intersectionArea = circleIntersection(
                shape1[0], shape1[1], shape1[2],
                shape2[0], shape2[1], shape2[2]
            );
        } else if (isRect1 && isRect2) {
            intersectionArea = rectangleIntersection(
                shape1[0], shape1[1], shape1[2], shape1[3],
                shape2[0], shape2[1], shape2[2], shape2[3]
            );
        } else {
            intersectionArea = monteCarloIntersection(shape1, isRect1, shape2, isRect2);
        }

        cout << (int)(intersectionArea + 0.5) << endl; // 四舍五入
    }
    return 0;
}

代码说明

1. 圆与圆相交：使用几何公式计算两圆的交集面积。
2. 矩形与矩形相交：直接计算重叠区域的面积。
3. 圆与矩形相交：采用蒙特卡洛方法，在放大的网格上采样估算面积。
4. 输入处理：根据输入类型读取参数，并调用相应的计算函数。
5. 输出：四舍五入后输出最接近的整数。

该方法确保了所有情况的正确计算，并在处理复杂形状（如圆与矩形）时提供了合理的近似解。