题解：P1302 可见矩形

superLouis · 2025-07-27 11:49:51 · 题解

题解：P1302 可见矩形

1. 题目大意

为了解决这个问题，我们需要计算从坐标原点 O(0,0) 可见的正方形数量。一个正方形 R 是从 O 点可见的，当且仅当存在其边上的两个不同点 A 和 B，使得 \triangle OAB 的内部与其他任何正方形都没有公共点（即不被其他正方形遮挡）。

2. 方法思路

每个正方形位于第一象限（坐标和边长均为正整数），且互不相交。从原点 O 观察每个正方形，它会覆盖一个连续的极角区间。我们需要确定在每个正方形的覆盖区间内，是否存在至少一个角度\theta，使得从 O 点出发沿 \theta 方向的射线首先碰到该正方形（即该正方形在该方向上未被其他正方形遮挡）。

在思考过程中注意以下三个关键点：

• 每个正方形覆盖的极角区间可以通过其左下角坐标 (x, y) 和边长 l 计算：最小角度 \theta_{min} 为 atan2(y, x+l)，最大角度 \theta_{max} 为 atan2(y+l, x)。
• 对于给定角度 \theta，射线上的点可表示为 (t\times\cos\theta, t\times\sin\theta)。正方形在该方向上的最小距离 t 为 \max(\frac{x}{\cos\theta}, \frac{y}{\sin\theta})。
• 一个正方形在角度 \theta 上未被遮挡的条件是：其最小距离 t_i 小于或等于其他所有在该角度上活跃（即 \theta 在其覆盖区间内）的正方形的最小距离 t_j。

我们可以采用采样法。对每个正方形，在其角度区间内均匀采样 200 个点（包括端点）。对于每个采样点 \theta，计算该正方形的最小距离 t_i，并检查是否所有其他活跃正方形的 t_j 均不小于 t_i（即 t_i 是最小的）。若存在这样的 \theta ，则该正方形可见。

为避免高精度浮点计算，使用适当容差（比如 10^{-8}）进行浮点数比较。采样点数量在精度和效率之间取得平衡，确保在合理时间内完成。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
const double eps = 1e-8;
int n, ans;
double x[maxn], y[maxn], l[maxn];
double mindeg[maxn], maxdeg[maxn];
bool see[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> l[i];
        mindeg[i] = atan2(y[i], x[i] + l[i]);
        maxdeg[i] = atan2(y[i] + l[i], x[i]);
    }
    for (int i = 0; i < n; i++) {
        double low = mindeg[i];
        double high = maxdeg[i];
        for (int k = 0; k < 200; k++) {
            double theta;
            if (k == 0) theta = low;
            else if (k == 199) theta = high;
            else theta = low + (high - low) * k / 199.0;
            double Cos = cos(theta);
            double Sin = sin(theta);
            double ti = max(x[i] / Cos, y[i] / Sin);
            bool flg = false;
            for (int j = 0; j < n; j++) {
                if (i == j || theta < mindeg[j] || theta > maxdeg[j]) continue;
                double tj = max(x[j] / Cos, y[j] / Sin);
                if (tj < ti - eps) {
                    flg = true;
                    break;
                }
            }
            if (!flg) {
                see[i] = true;
                break;
            }
        }
    }
    for (int i = 0; i < n; i++)
        if (see[i]) ans++;
    cout << ans << "\n";
    return 0;
}

用时 153ms 跑得飞快。