P5975

lidagua1005 · 2023-11-27 13:43:39 · 题解

part.1 题意

这道题就是让你用最少的矩形囊括所有的点。

part.2 思路

不难想到在诸多的点中，越高的点越难被装进矩形里。因为在矩形面积一定时，高越高，宽越短。所以我们可以优先考虑这部分点。

采用双关键字排序，第一为点的 y 坐标，第二为点的 x 坐标，优先处理下标小的点即可。

我们可以用每个点被包含所需的矩形的极限坐标来看包含该点所需的矩形是否可以包含其它矩形，这就可以使用贪心来实现。

对每个点，先预处理出它被包含所需的矩形的极限坐标。需使用时，直接调取即可。

part.3 代码

#include<bits/stdc++.h>
using namespace std;
struct node//储存每个点的信息 
{
    int x,y;//x,y坐标 
    double qj_l,qj_r;//包含所需的矩形的极限坐标 
    bool dn;//点是否被算过了 
}f[101];
bool cmp(node x,node y)//双关键字比较 
{
    if(x.y!=y.y) return x.y>y.y;
    return x.x<y.x;
}
int main()
{
    int n,a;cin>>n>>a;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i].x>>f[i].y;
        f[i].qj_l=f[i].x*1.0-a*1.0/f[i].y;//预处理矩形坐标 
        f[i].qj_r=f[i].x*1.0+a*1.0/f[i].y;
        f[i].dn=0;
    }
    sort(f+1,f+n+1,cmp);//排序 
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(f[i].dn) continue;//如果算过了，就跳过 
        ans++;//否则ans++
        f[i].dn=1;
        bool flg=0;
        for(int j=1;j<=n;j++)
        {
            if(f[j].dn) continue;
            if(f[i].qj_r>=f[j].x&&f[i].qj_l<=f[j].x)//找到所有被包含的点 
            {
                f[j].dn=1;
                if(!flg)//找到所有被包含的点中最高点，必须要包含它 
                {
                    if(f[j].x>=f[i].x)
                    {
                        f[i].qj_l+=f[j].x-f[i].x;
                    }
                    else
                    {
                        f[i].qj_r-=f[j].x-f[i].x;
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}