这道题的思路挺简单的……就是可以证明如果要覆盖一个区域内的点,那么一定有一个正方形在这“区域内的点所围成的最大矩形的四个角中的一个”(不要吐槽很多的“的”……),对于长度r是否可以覆盖整个区域内的点,只需要先枚举第一个矩形在“区域内的点所围成的最大矩形的四个角中的哪一个”,然后再枚举下一个点在“区域内的剩余点所围成的最大矩形的四个角中的哪一个”第三个正方形就直接判断余下的点的最大最小差值是否小于r就行了……再然后就直接二分答案了……然后,注意一种情况,就是出现一个或者两个矩形就可以覆盖完整个区域点的情况(可能是因为我傻×于是就被这里坑了一下)……
type
arr=record
x,y:longint;
end;
var
a:array[..]of arr;
i,j,k,l,r,n,mid,maxx,minx,maxy,miny:longint;
vs:array[..]of longint; procedure find(var x1,x2,y1,y2:longint);
begin
x1:=-maxlongint;
x2:=maxlongint;
y1:=-maxlongint;
y2:=maxlongint;
for i:= to n do if vs[i]= then
begin
if a[i].x>x1 then x1:=a[i].x;
if a[i].x<x2 then x2:=a[i].x;
if a[i].y>y1 then y1:=a[i].y;
if a[i].y<y2 then y2:=a[i].y;
end;
end; function dfs(x,y:longint):boolean;
var
maxx,minx,maxy,miny:longint;
begin
find(maxx,minx,maxy,miny);
if minx=maxlongint then exit(true);
if y= then begin
if (maxx-minx<=x) and (maxy-miny<=x) then exit(true);
exit(false);
end; for i:= to n do
if vs[i]= then
if (minx+x>=a[i].x) and (miny+x>=a[i].y) then vs[i]:=y;
if dfs(x,y+) then exit(true);
for i:= to n do
if vs[i]=y then vs[i]:=; for i:= to n do
if vs[i]= then
if (minx+x>=a[i].x) and (maxy-x<=a[i].y) then vs[i]:=y;
if dfs(x,y+) then exit(true);
for i:= to n do
if vs[i]=y then vs[i]:=; for i:= to n do
if vs[i]= then
if (maxx-x<=a[i].x) and (miny+x>=a[i].y) then vs[i]:=y;
if dfs(x,y+) then exit(true);
for i:= to n do
if vs[i]=y then vs[i]:=; for i:= to n do
if vs[i]= then
if (maxx-x<=a[i].x) and (maxy-x<=a[i].y) then vs[i]:=y;
if dfs(x,y+) then exit(true);
for i:= to n do
if vs[i]=y then vs[i]:=;
exit(false);
end; begin
readln(n);
for i:= to n do
readln(a[i].x,a[i].y);
fillchar(vs,sizeof(vs),);
find(maxx,minx,maxy,miny);
l:=;
if maxx-minx>maxy-miny
then r:=maxx-minx
else r:=maxy-miny;
while l<=r do begin
fillchar(vs,sizeof(vs),);
mid:=(l+r)>>;
if dfs(mid,) then r:=mid-
else l:=mid+;
end;
writeln(l);
readln;
end.
【以前的空间】bzoj 1052 [HAOI2007]覆盖问题的更多相关文章
-
BZOJ 1052: [HAOI2007]覆盖问题
BZOJ 1052: [HAOI2007]覆盖问题 题意:给定平面上横纵坐标在-1e9~1e9内的20000个整数点的坐标,用三个大小相同边平行于坐标轴的正方形覆盖(在边界上的也算),问正方形的边长最 ...
-
[BZOJ 1052][HAOI2007]覆盖问题(二分答案)
题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1052 分析: 挺有想法的一道题,先二分答案ans,主要是判断的问题. 首先可以弄出把所 ...
-
BZOJ 1052 HAOI2007 覆盖问题 二分法答案+DFS
标题效果:特定n点.涵盖所有的点与同方三面.斧头要求方垂直边界,最小平方的需求方长值 最大值至少.答案是很明显的二分法 但验证是一个问题 考虑仅仅有三个正方形,故用一个最小矩形覆盖这三个正方形时至少有 ...
-
【BZOJ 1052】 1052: [HAOI2007]覆盖问题 (乱搞)
1052: [HAOI2007]覆盖问题 Description 某人在山上种了N棵小树苗.冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄 膜把这些小树遮盖起来,经过一番长久的 ...
-
【BZOJ】1052: [HAOI2007]覆盖问题
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1052 大概自己YY了个贪心然后过了... 二分答案,考虑如何check: 找到一个最小的矩 ...
-
【BZOJ】1052: [HAOI2007]覆盖问题(贪心)
http://www.lydsy.com/JudgeOnline/problem.php?id=1052 首先膜拜题解orz,表示只能想到二分... 贪心就是每一次找到一个最小的能包围所有点的矩阵,然 ...
-
1052: [HAOI2007]覆盖问题 - BZOJ
Description 某人在山上种了N棵小树苗.冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定用3个L*L的正方形塑料薄膜将小 ...
-
[BZOJ1052][HAOI2007]覆盖问题 二分+贪心
1052: [HAOI2007]覆盖问题 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2053 Solved: 959 [Submit][Sta ...
-
二分判定 覆盖问题 BZOJ 1052
//二分判定 覆盖问题 BZOJ 1052 // 首先确定一个最小矩阵包围所有点,则最优正方形的一个角一定与矩形一个角重合. // 然后枚举每个角,再解决子问题 #include <bits/s ...
随机推荐
-
QT报错Error processing
执行命令:qmake modbus_ups_mlrl.pro modbus_ups_mlrl.pro文件内容: TEMPLATE = vclib CONFIG +=qt debug thread QT ...
-
Python学习(3)变量类型
目录 变量赋值 多个变量赋值 标准数据类型 Python数字 Python字符串 Python列表 Python元组 Python元字典 Python数据类型转换 type数据类型查看 变量赋值 Py ...
-
redo文件三
switch logfile是一种昂贵的操作,在进行日志切换的时候,是不允许生成新的redo信息 在前台进程生成redo日志信息的时候,此时redo buffer已经分配了空间,并且在当前的redo日 ...
-
屏蔽Codeforces做题时的Problem tags提示
当在Codeforces上做题的时,有时会无意撇到右侧的Problem tags边栏,但是原本并不希望能够看到它. 能否把它屏蔽了呢?答案是显然的,我们只需要加一段很短的CSS即可. span.tag ...
-
无法加载协定为“XXXWebServiceSoap”的终结点配置部分,因为找到了该协定的多个终结点配置
错误描述:无法加载协定为“XXXWebServiceSoap”的终结点配置部分,因为找到了该协定的多个终结点配置.请按名称指示首选的终结点配置部分. 错误原因:该webservce在web.confi ...
-
C# winform DatagridView 的简单操作
数据显示操作: dgBill.Columns[0].DataPropertyName = "key1"; dgBill.Columns[1].DataPropertyName = ...
-
敏捷冲刺每日报告五(Java-Team)
第五天报告(10.29 周日) 团队:Java-Team 成员: 章辉宇(284) 吴政楠(286) 陈阳(PM:288) 韩华颂(142) 胡志权(143) github地址:https://gi ...
-
痞子衡嵌入式:语音处理工具Jays-PySPEECH诞生记(1)- 环境搭建(Python2.7.14 + PyAudio0.2.11 + Matplotlib2.2.3 + SpeechRecognition3.8.1 + pyttsx3 2.7)
大家好,我是痞子衡,是正经搞技术的痞子.今天痞子衡给大家介绍的是语音处理工具Jays-PySPEECH诞生之环境搭建. 在写Jays-PySPEECH时需要先搭好开发环境,下表列出了开发过程中会用到的 ...
-
C#学习笔记-DataTable导出到EXCEL(一)
public void DataTabletoExcel(DataTable dt, string path) { StreamWriter sw = new StreamWriter(path, f ...
-
【RAY TRACING THE REST OF YOUR LIFE 超详解】 光线追踪 3-7 混合概率密度
Preface 注:鉴于很多网站随意爬取数据,可能导致内容残缺以及引用失效等问题,影响阅读,请认准原创网址: https://www.cnblogs.com/lv-anchoret/category ...