P7181题解

· · 题解

这个题是波罗的海 2004 年信息竞赛的题目，放到现在应该是一道普及 + 的题目。

我们来看看 n=1 时的情形。例如， x_{\mathrm{max}}=y_{\mathrm{max}}=11, 矩形左下角和右上角分别为 (4,2),\ (5,7) 时，我们来直观地看一下哪些边界点是满足它和原点的连线与矩形相交的。

这意味着我们只需考虑矩形的左上顶点和右下顶点，将原点与此二顶点相连的射线与边界交于两点，这两点之间的边界点中的整点即为我们所求的 n=1 时的点。

则题目变成：给定 n 个区间，求一个整点，使得任何其他的点所被包括的区间数量均不大于该整点。这即是一道较低难度的模板题了。

#include <bits/stdc++.h>
using namespace std;
struct el // 区间
{
    int h;//区间的整点边界
    int tp;//是区间左界还是右界
}m[20001];//区间有两个界，所以是10000*2
struct ju//矩形
{
    int x_1;
    int y_1;
    int x_2;
    int y_2;
}mas[10001];
int len,pried;
int maxx,maxy,n;
inline bool cmp(el A,el B)//排序
{
    if(A.h==B.h)    return A.tp>B.tp;
    else return A.h<B.h;
}
#define QKSORT(l,r) sort(m+(l),m+(r),cmp)
inline void add(int x,int y,int tp)
{
    double a;
    m[++len].tp=tp;
    if(x*1LL*maxy<=y*1LL*maxx)  m[len].h=maxy;//只考虑外边界矩形的某一边
    else
    {
        a=(long long)maxx*1LL*y;
        a=a*1.0/x;
        if(tp>0)    m[len].h=ceil(a-0.0001);//防止奇怪的浮点数出错
        else    m[len].h=floor(a+0.0001);
    }
}
int sum(int* x,int* y)
{
    int k,mx,mxh;
    len=0;
    for(int i=1;i<=n;i++)
    {
        if((long long)1LL*mas[i].x_1*maxy<1LL*mas[i].y_1*maxx)  continue;//它属于另外一边
        add(mas[i].x_1,mas[i].y_1,1);
        add(mas[i].x_2,mas[i].y_2,-1);
    }
    if(len>0)   QKSORT(1,len);
    k=0,mx=0,mxh=0;
    for(int i=1;i<=len;i++)
    {
        k+=m[i].tp;
        if(k>mx)    mx=k,mxh=m[i].h;
    }
    *x=maxx,*y=mxh;
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>maxx>>maxy>>n;
    int tmp=0,i=1;
    for(int j=1;j<=n;j++)
    {
        cin>>mas[i].x_1>>mas[i].y_1>>mas[i].x_2>>mas[i].y_2;
        if(mas[i].x_1==0 && mas[i].y_1==0)
            pried++;
        else
        {
            swap(mas[i].x_1,mas[i].x_2);
            i++,tmp++;          
        }
    }
    n=tmp;
    int ats,ax=0,ay=0,bx=0,by=0;
    ats=sum(&ax,&ay);
    swap(maxx,maxy);//全部取反，考虑另一边
    for(int i=1;i<=n;i++)
    {
        swap(mas[i].x_1,mas[i].y_1);
        swap(mas[i].x_2,mas[i].y_2);
        swap(mas[i].x_1,mas[i].x_2);
        swap(mas[i].y_1,mas[i].y_2);
    }
    tmp=sum(&by,&bx);
    if(ats<tmp) ats=tmp,ax=bx,ay=by;//合并两边，得到答案
    cout<<ats+pried<<' '<<ax<<' '<<ay<<endl;
    return 0;
}