P7216 [JOISC2020] 美味しい美味しいハンバーグ 题解
syf2008
·
·
题解
本解法非正解，但是能过所有数据（包括 loj 加强版），欢迎 hack
题意
平面上给定 n 个矩形，选择 k 个点，使得每个矩形内部都至少被选择一个点。
## Solution
发现这个 $k$ 特别小，可以考虑随机。
我们可以先钦定 $k$ 个矩形为特殊矩形（在每个矩形上都要至少选一个点），然后其它矩形与特殊矩形做矩形交，让这些矩形和任意与它有交的特殊矩形交集为合并的结果。
具体的，可以考虑每次随机序列，这样虽然能过原题数据，但是在 loj 的加强版会寄，即使你加入去重，去掉所有重复的矩形，通过了 loj 的 hack，其实还是错的。
## mkdata:
```cpp
#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:
```cpp
#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:;
}
}
```