p1378

问题分析

在一个长方形框内，有 N 个相异的点。在每个点上依次放置一个油滴，油滴会扩展直到接触到其他油滴或框子的边界。要求找出放置顺序，使得所有油滴占据的总面积最大（即剩余空间最小）。油滴是圆形且不会融合，必须等一个油滴完全扩展后才能放置下一个。

关键点：

• 每个油滴的半径取决于放置时的环境：到边界的最小距离和到已放置油滴的距离。
• 先放置的油滴会限制后放置油滴的半径。
• 为了最大化总面积，应优先放置那些在无约束时能扩展得更大的点（即到边界距离较大的点），因为它们在无约束时能占据更大面积，即使覆盖后续点导致其半径为0，总面积也可能更大。

算法思路

1. 计算每个点的初始最大半径：对于每个点，计算其到长方形四条边界的最小距离（即单独放置时能扩展的最大半径）。
2. 按初始半径降序排序：优先放置初始半径大的点，使其在无其他油滴约束时达到最大可能半径。
3. 依次放置油滴并计算实际半径：
   • 对于当前点，其实际半径受限于：
     • 初始最大半径（到边界的最小距离）。
     • 到每个已放置油滴的距离减去该油滴的半径（确保不重叠）。
   • 实际半径取上述所有约束的最小值，若为负则置0（表示被覆盖）。
4. 计算总面积和剩余空间：
   • 所有油滴面积之和 = Σ(π * r_i²)。
   • 长方形面积 = (x_right - x_left) * (y_top - y_bottom)。
   • 剩余空间 = 长方形面积 - 油滴总面积（四舍五入取整）。

优化

• 提前终止：在计算当前点的实际半径时，若半径已降至0或负，可提前终止内层循环（后续约束不会增大半径）。
• 浮点误差处理：剩余空间若为负（因浮点误差），置0后再四舍五入。

复杂度

• 时间复杂度：O(N²)，其中 N 为点数。排序 O(N log N)，放置油滴时每点需检查所有已放置点。
• 空间复杂度：O(N)，存储点和半径。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
    double r0;
    int id;
};

int main() {
    int N;
    cin >> N;
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double x_left = min(x1, x2);
    double x_right = max(x1, x2);
    double y_bottom = min(y1, y2);
    double y_top = max(y1, y2);

    vector<Point> pts;
    for (int i = 0; i < N; i++) {
        double x, y;
        cin >> x >> y;
        double d1 = x - x_left;
        double d2 = x_right - x;
        double d3 = y - y_bottom;
        double d4 = y_top - y;
        double r0 = min(min(d1, d2), min(d3, d4));
        pts.push_back({x, y, r0, i});
    }

    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.r0 > b.r0;
    });

    vector<double> radius(N, 0.0);

    for (int i = 0; i < N; i++) {
        double r = pts[i].r0;
        for (int j = 0; j < i; j++) {
            double dx = pts[i].x - pts[j].x;
            double dy = pts[i].y - pts[j].y;
            double d = sqrt(dx * dx + dy * dy);
            double candidate = d - radius[pts[j].id];
            if (candidate < r) {
                r = candidate;
            }
            if (r <= 0) {
                break;
            }
        }
        if (r < 0) {
            r = 0;
        }
        radius[pts[i].id] = r;
    }

    const double PI = acos(-1.0);
    double total_circle_area = 0.0;
    for (int i = 0; i < N; i++) {
        total_circle_area += PI * radius[i] * radius[i];
    }

    double rect_area = (x_right - x_left) * (y_top - y_bottom);
    double remaining = rect_area - total_circle_area;
    if (remaining < 0) {
        remaining = 0;
    }
    long ans = lround(remaining);
    cout << ans << endl;

    return 0;
}

放置油滴：

• 遍历排序后的点，对每个点计算实际半径：
  • 初始为 r0。
  • 遍历所有已放置点，更新半径为到已放置点距离减去其半径的最小值。
  • 若半径降至0或负，提前终止内层循环。
• 最终半径不小于0。

面积计算：

• 油滴总面积 = Σ(π * r²)。
• 剩余空间 = 长方形面积 - 油滴总面积。
• 处理浮点误差（剩余空间非负），四舍五入输出。