先二分边长,然后按这样的策略判断:正方形肯定是选边上的四个角,枚举第一块在哪个角,再算一边四个角,再枚举第二块,判断剩下的能不能被第三块覆盖
const int N = 20010; pair<int, int> Data[N]; int n; inline void Input() { scanf("%d", &n); For(i, 1, n) scanf("%d%d", &Data[i].ft, &Data[i].sd); } int Mark[N]; inline bool Solve(int R, int Dep) { int Up = -MIT, Down = MIT, Left = MIT, Right = -MIT, flag = 0; For(i, 1, n) if(!Mark[i]) { flag = 1; int X = Data[i].ft, Y = Data[i].sd; Up = max(Up, Y), Down = min(Down, Y), Left = min(Left, X), Right = max(Right, X); } if(!flag) return 1; if(Dep > 2) return R >= max(Up - Down, Right - Left); else { int Ox1, Ox2, Oy1, Oy2; For(type, 1, 4) { if(type == 1) Ox1 = Left, Ox2 = Left + R, Oy1 = Down, Oy2 = Down + R; else if(type == 2) Ox1 = Left, Ox2 = Left + R, Oy1 = Up - R, Oy2 = Up; else if(type == 3) Ox1 = Right - R, Ox2 = Right, Oy1 = Down, Oy2 = Down + R; else Ox1 = Right - R, Ox2 = Right, Oy1 = Up - R, Oy2= Up; // mark For(i, 1, n) if(!Mark[i]) { pair<int, int> *Dat = &Data[i]; if(Dat->ft >= Ox1 && Dat->ft <= Ox2 && Dat->sd >= Oy1 && Dat->sd <= Oy2) Mark[i] = Dep; } if(Solve(R, Dep + 1)) return 1; For(i, 1, n) if(Mark[i] == Dep) Mark[i] = 0; } } return 0; } inline void Solve() { // get MaxDis int Up = -MIT, Down = MIT, Left = MIT, Right = -MIT; For(i, 1, n) { int X = Data[i].ft, Y = Data[i].sd; Up = max(Up, Y), Down = min(Down, Y), Left = min(Left, X), Right = max(Right, X); } int mid, ans = INF, lef = 0, rig = max(Up - Down, Left - Right); while(lef <= rig) { mid = (lef + rig) >> 1; clr(Mark, 0); if(Solve(mid, 1)) rig = (ans = mid) - 1; else lef = mid + 1; } printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE SETIO("1052"); #endif Input(); Solve(); return 0; }
相关推荐
BZOJ原题-BZOJP1000-P2000的题目,下载后可以离线做题。
八中OJ,又简作BZOJ,以原题巨多而著称,该数据为BZOJ上的1000-1109和1130-1139的测试数据节点,没有题目,有需要题目的可以到https://hydro.ac/d/bzoj/p网站查找对应的题目。
「BZOJ1053」反素数/「Violet5」樱花 详细题解
BZOJ原题-BZOJP3001-P4000的题目,下载后可以离线做题。
bzoj部分数据.
BZOJ3230相似子串的测试数据,希望能够帮到大家。
#BZOJ Problem Rankrank.cpp 程序文件data.dat bzoj题库数据done.dat AC过的题,初始可以把所有A过的题粘进去,正常退出的话自动维护。black.dat 黑名单。选题时会跳过。错题、神题、没题面、不想做等等。//Thank ...
BZOJ网站镜像,对于经常挂掉的BZOJ真是刷题必备啊!
BZOJ原题-BZOJP2001-P3000的题目,下载后可以离线做题。
BZOJ平台全部代码,解压到一个文件夹在打开使用。BZOJ平台全部代码,解压到一个文件夹在打开使用。
BZOJ原题-BZOJP4001-P4406的题目,下载后可以离线做题。
bzoj1878数据(莫队)详细题解:http://blog.csdn.net/boyxiejunboy/article/details/50611972
题解 , 文档 , 资料 BZOJ 泡泡堂
BZOJ省选十连测题面,只有题面!!!!!,请自行到BZOJ上进行提交,上传目的是提供离线的一个题目
ZOJCH是BZOJ题库的离线版
CreationAugust 的BZOJ代码合集 【Written by CreationAugust】
本模板为 BZOJ3224:文艺平衡树 的源程序 含各种操作,旋转,插入,删除,求前驱,后继,查询值为x的数的排名,查询排名为k的数,求最大值,最小值……
八中OJ所有题目
Description 背景 众所周知,DZY是个大学霸,精通数理化。有天,吉丽拿着一道物理题目去问DZY,DZY很快就秒了这题,但是懒得算了,就让你...当然,为了考察你的随机应变能力,吉丽会在问问题的时候不时地增加新的小球。
bzoj FFT 的模版