这么好（shui）的题目怎么能不上随机化搜索呢
//思路：随机化搜索+贪心（从今年D1可以看出贪心是多么重要的能力（然而D1AK也救不了我D2爆炸QAQ（事实证明D2还是多打暴力为上策）））
//每次以一定的概率进行贪心选择或随机选择
//贪心策略为将这个点加入一个矩形，选择代价最小的一个（很明显是错的，所以要随机化搜索辅助）
#include<bits/stdc++.h>
using namespace std;
int ans=2000000000;
int n,k;
struct lj
{
int x,y;
}point[59];
int x[5],xx[5],y[5],yy[5];//万能头不能用y1，所以就叫y,yy吧ovo
int main()
{
srand(time(0));
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&point[i].x,&point[i].y);
}
for(int iii=1;iii<=250000;++iii)
{
srand(rand());//其实没用哦0.0
random_shuffle(point+1,point+n+1);//随机序列，左闭右开
for(int j=1;j<=k;j++)//初始化，每个矩阵里至少要有一个点，也是为什么要随机化序列的原因之一
{
x[j]=xx[j]=point[j].x;
y[j]=yy[j]=point[j].y;
}
for(int j=k+1;j<=n;j++)
{
int mn=2000000000,cs;
if(rand()%100+1<=70)//以70%的概率选择贪心，似乎70—90的概率都能过
{
for(int ii=1;ii<=k;ii++)
{
if((max(xx[ii],point[j].x)-min(x[ii],point[j].x))*(max(yy[ii],point[j].y)-min(y[ii],point[j].y))-(xx[ii]-x[ii])*(yy[ii]-y[ii])<mn)
{
mn=(max(xx[ii],point[j].x)-min(x[ii],point[j].x))*(max(yy[ii],point[j].y)-min(y[ii],point[j].y))-(xx[ii]-x[ii])*(yy[ii]-y[ii]);
cs=ii;
}
}
}
else cs=rand()%k+1;//不然随机
//改变被选择的矩形的大小
xx[cs]=max(xx[cs],point[j].x);
x[cs]=min(x[cs],point[j].x);
yy[cs]=max(yy[cs],point[j].y);
y[cs]=min(y[cs],point[j].y);
}
int tot=0;
for(int i=1;i<=k;i++)
{
tot+=(xx[i]-x[i])*(yy[i]-y[i]);//统计答案
}
for(int i=1;i<k;i++)
{
for(int j=i+1;j<=k;j++)
{
if((x[i]==x[j]||x[i]==xx[j]||xx[i]==x[j]||xx[i]==xx[j])&&(y[i]==y[j]||y[i]==yy[j]||yy[i]==y[j]||yy[i]==yy[j])) tot=200000000;//判断顶点重合
if((x[i]==x[j]||x[i]==xx[j]||xx[i]==x[j]||xx[i]==xx[j])&&((y[i]<yy[j]&&yy[i]>y[j])||(y[j]<yy[i]&&yy[j]>y[i]))) tot=200000000;//纵边重合
if((y[i]==y[j]||y[i]==yy[j]||yy[i]==y[j]||yy[i]==yy[j])&&((x[i]<xx[j]&&xx[i]>x[j])||(x[j]<xx[i]&&xx[j]>x[i]))) tot=200000000;//横边重合
}
}
ans=min(ans,tot);
}
cout<<ans;
return 0;
}
突然发现自己唯二的题解都是些奇奇怪怪的算法呢…
请大家尽情hack吧ovo
