题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1052
对于这样的问题，直接就能想到二分
这个做法我之前以为会TLE，没想到居然跑的很快..
我们发现，对于三个正方形，一定至少有一个是放在角落的
先二分边长，再尝试着把正方形分别放到四个角落
然后暴力地去覆盖点，对于两个正方形来说也一定至少有一个在角落，所以接着暴力覆盖
剩下1个正方形时，判断一下能不能完全覆盖就好
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<bits/stdc++.h> #define maxn 20020 #define ll long long using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ int x,y; }; int n; point p[maxn]; bool vis[maxn]; inline void cal(int &h1,int &h2,int &w1,int &w2){ h1=w1=INT_MAX; h2=w2=INT_MIN; for(int i=1; i<=n; i++){ if(vis[i])continue; h1=min(h1,p[i].x); h2=max(h2,p[i].x); w1=min(w1,p[i].y); w2=max(w2,p[i].y); } } inline void color(int x,int y,int l,bool k){ for(int i=1; i<=n; i++){ if(p[i].x>=x && p[i].x<=x+l && p[i].y>=y && p[i].y<=y+l)vis[i]=k; } } inline bool check(int l,int num){ int h1,h2,w1,w2; cal(h1,h2,w1,w2); if(h1==INT_MIN)return true; if(num==3 && max(h2-h1,w2-w1)<=l)return true; else if(num==3)return false; color(h1,w1,l,1); if(check(l,num+1))return true; color(h1,w1,l,0); color(h1,w2-l,l,1); if(check(l,num+1))return true; color(h1,w2-l,l,0); color(h2-l,w1,l,1); if(check(l,num+1))return true; color(h2-l,w1,l,0); color(h2-l,w2-l,l,1); if(check(l,num+1))return true; color(h2-l,w2-l,l,0); return false; } int main(){ n=rd(); for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd(); int l=0,r=INT_MAX,ans=0; while(l<=r){ int mid=((ll)l+r)/2ll; memset(vis,0,sizeof(vis)); if(check(mid,1))ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; } |
