题解：P1302 可见矩形

Thronf · 2024-07-20 11:51:38 · 题解

本蒟蒻的第一篇题解。

推导

首先，对于本题，很显然正方形都在第一象限，那么，可以用直线去模拟每一条“视线”。

你可以理解为固定你的坐标 (0,0) ，同时转头，从 x 轴逆时针转到 y 轴。

然后对于每一根直线，通过区间判断来找出每条直线所“接触”的第一个正方形（这就需要你进行排序），把正方形打上标记（用结构体就可以搞定），最后用一个量来统计数量。

最后输出答案。

几个问题（dalao 跳过）

1. 排序关键字

   这道题的调式点在于排序和精度，而排序又是比较难想到的，主要有以下两种错误排序：

• 顶点排序

  以左下角顶点为关键字，比较该点到 O 点的距离，从小到大排序。 (70pts)

  • 斜线排序

    以 X+Y 为关键字进行排序。 (80pts)

  显然，前面两组排序方式较为片面，所以，综合多方面考虑，那么最显而易见的就是以 X+Y+L 进行排序。

2. 精度选择

   对于查找间隔，很多同志可能会先以斜率为查找对象，然而并不行，因为这样的话，对于与 x 轴夹角小于 \frac{\pi}{4} 的直线间隔太大，而大于 \frac{\pi}{4} 的直线又间隔太小，如果要达到要求的精度 (\frac{1}{10000},10000) 就一定会 TLE ，所以考虑用角度作为查找对象。这个精度大家要慢慢去找，我这里有个参考值是 \frac{\pi}{180000} 。

附上代码

#include<bits/stdc++.h>
#define int long long // 防止忘记开long long 
//#define for(i,a,b,c,d) for(int i=a;i d b;i+=c)
using namespace std;
const double pi=3.141592653589793238462643383279502884197169399375105; // 圆周率 
struct sqare{
    double x1,y1,x2,y2;
    bool can;
}a[10005]; // 存储正方形（ can 用来打标记） 
int n,ans;
int check(int i,double k) // 判断是否经过正方形 
{
    if(a[i].x1*k<a[i].y2&&(a[i].x2*k>a[i].y1)) // 自己画图像 
    {
        if(!a[i].can)
        {
            a[i].can=1;
            return 1;
        }
        else
            return 2; // 如果已经有了隔挡的正方形 
    }
    return 0;
}
bool cmp(sqare a,sqare b) // 排序用
{
    return (a.x1+a.y2)<(b.x1+b.y2);
}
signed main() // 用了 #define int long long 就不能再用int main（）了 
{
    ios::sync_with_stdio(0); // 关缓冲区 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        double x,y,l; // 输入 
        cin>>x>>y>>l;
        a[i].x1=x,a[i].x2=x+l,a[i].y1=y,a[i].y2=y+l;
    }
    sort(a+1,a+1+n,cmp); // 排序 
    for(double thita=pi/180000;thita<pi/2;thita+=pi/180000) // 枚举角度 
    {
        double k=tan(thita); // 算斜率 
        for(int i=1;i<=n;i++)
        {
            int c=check(i,k);
            if(c==1)
            {
                ans++;
                break;
            }
            else if(c==2)
                break;
        }
    }
    cout<<ans; 
    return 0; 
}