自动搬运

查看原文

来自洛谷，原作者为

	syf2008 **

搬运于2025-08-24 22:27:46，当前版本为作者最后更新于2023-05-03 14:20:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本解法非正解，但是能过所有数据（包括 loj 加强版），欢迎 hack

题意

平面上给定 $n$ 个矩形，选择 $k$ 个点，使得每个矩形内部都至少被选择一个点。

$n\le 2 \times 10^5$，$k\le 4$，保证数据有解。

Solution

发现这个 $k$ 特别小，可以考虑随机。

我们可以先钦定 $k$ 个矩形为特殊矩形（在每个矩形上都要至少选一个点），然后其它矩形与特殊矩形做矩形交，让这些矩形和任意与它有交的特殊矩形交集为合并的结果。

具体的，可以考虑每次随机序列，这样虽然能过原题数据，但是在 loj 的加强版会寄，即使你加入去重，去掉所有重复的矩形，通过了 loj 的 hack，其实还是错的。

mkdata:

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n=2e5,k=2;
	cout<<n<<' '<<k<<'\n';
	for(int i=1;i<=99999;i++)
	cout<<i<<" 1 500000000 1000000000\n";
	for(int i=100000;i<=199999;i++)
	cout<<"500000000 "<<i-99999<<" 1000000000 999999999\n";
	cout<<"1000000000 1000000000 1000000000 1000000000\n";
}

所以，我们考虑更加优秀的随机。

我们发现，如果重构整个序列，其实是不优的，所以我们可以把第一个无法与特殊矩形相交的矩形向前随机交换，这样就可以通过加强版数据了。

code:

#include<bits/stdc++.h>
const int N=2e5+5;
using namespace std;
struct meat{int x,y,xx,yy;}a[N],b[10];
meat jiao(meat a,meat b)//求矩形交
{return (meat){max(a.x,b.x),max(a.y,b.y),min(a.xx,b.xx),min(a.yy,b.yy)};}
mt19937 rnd(time(0));
int n,k,tmp;
double S(meat a){return 1.0*(a.yy-a.y+1)*(a.xx-a.x+1);}
double calc(meat a,meat b)
{   
    meat temp=jiao(a,b);
    if(temp.x>temp.xx||temp.y>temp.yy)return -1;
    return S(temp)/S(a);
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y>>a[i].xx>>a[i].yy;
    while(1)
    {
        for(int i=1;i<=k;i++)b[i]=a[i];
        for(int i=k+1,id;i<=n;i++)
        {
            id=0;
            for(int j=1;j<=k;j++)
            {
                double now=calc(b[j],a[i]);
                if(now>0)id=j;
            }
            if(!id){swap(a[i],a[rnd()%(i-1)+1]);goto ff;}//无法与特殊矩形相交，向前随机交换
            b[id]=jiao(b[id],a[i]);//用交集替换
        }
        for(int i=1;i<=k;i++)
		if(!b[i].x)cout<<1<<' '<<1<<'\n';//如果 n<k 那么就会有点空出来，直接随便放在任意位置即可 
	else cout<<b[i].x<<' '<<b[i].y<<'\n';//输出合法解
        return 0;
        ff:;
    }
}