专栏文章

题解：P1302 可见矩形

ssuperLouis
P1302题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopdxug
此快照首次捕获于
2025/12/02 22:58
3 个月前
此快照最后确认于
2025/12/02 22:58
3 个月前
查看原文

题解：P1302 可见矩形

1. 题目大意

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

2. 方法思路

每个正方形位于第一象限（坐标和边长均为正整数），且互不相交。从原点 OO 观察每个正方形，它会覆盖一个连续的极角区间。我们需要确定在每个正方形的覆盖区间内，是否存在至少一个角度θ\theta，使得从 OO 点出发沿 θ\theta 方向的射线首先碰到该正方形（即该正方形在该方向上未被其他正方形遮挡）。
在思考过程中注意以下三个关键点：
  • 每个正方形覆盖的极角区间可以通过其左下角坐标 (x,y)(x, y) 和边长 ll 计算：最小角度 θmin\theta_{min} 为 atan2(y, x+l)，最大角度 θmax\theta_{max} 为 atan2(y+l, x)。
  • 对于给定角度 θ\theta，射线上的点可表示为 (t×cos⁡θ,t×sin⁡θ)(t\times\cos\theta, t\times\sin\theta)。正方形在该方向上的最小距离 tt 为 max⁡(xcos⁡θ,ysin⁡θ)\max(\frac{x}{\cos\theta}, \frac{y}{\sin\theta})。
  • 一个正方形在角度 θ\theta 上未被遮挡的条件是：其最小距离 tit_i 小于或等于其他所有在该角度上活跃（即 θ\theta 在其覆盖区间内）的正方形的最小距离 tjt_j。
我们可以采用采样法。对每个正方形，在其角度区间内均匀采样 200200 个点（包括端点）。对于每个采样点 θ\theta，计算该正方形的最小距离 tit_i，并检查是否所有其他活跃正方形的 tjt_j 均不小于 tit_i（即 tit_i 是最小的）。若存在这样的 θ\theta ，则该正方形可见。
为避免高精度浮点计算，使用适当容差（比如 10−810^{-8}）进行浮点数比较。采样点数量在精度和效率之间取得平衡，确保在合理时间内完成。

代码实现

CPP
#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 跑得飞快。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...