BZOJ 1052 HAOI2007 覆盖问题 二分法答案+DFS

BZOJ 1052 HAOI2007 覆盖问题 二分法答案+DFS

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

标题效果:特定n点。涵盖所有的点与同方三面。斧头要求方垂直边界,最小平方的需求方长值

最大值至少。答案是很明显的二分法

但验证是一个问题

考虑仅仅有三个正方形,故用一个最小矩形覆盖这三个正方形时至少有一个在角上 若有四个正方形该结论不成立

于是我们採用DFS的方式 每次用一个最小的矩形覆盖全部的点,枚举矩形的四个角 将正方形填进去

因为最大深度是3,所以时间上全然能够承受

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 20100
using namespace std;
struct abcd{
	int x,y;
}points[M];
int n,v[M];
int stack[M],top;
bool DFS(int L,int dpt)
{
	int i,j,bottom=top;
	int minx=0x3f3f3f3f,maxx=0xefefefef;
	int miny=0x3f3f3f3f,maxy=0xefefefef;
	if(top==n)
		return true;
	if(dpt==3)
		return false;
	for(i=1;i<=n;i++)
		if(!v[i])
		{
			minx=min(minx,points[i].x);
			maxx=max(maxx,points[i].x);
			miny=min(miny,points[i].y);
			maxy=max(maxy,points[i].y);
		}
	int dx[]={minx,minx,maxx-L,maxx-L};
	int dy[]={miny,maxy-L,miny,maxy-L};
	for(j=0;j<4;j++)
	{
		for(i=1;i<=n;i++)
			if(!v[i])
				if(points[i].x>=dx[j]&&points[i].x<=dx[j]+L)
					if(points[i].y>=dy[j]&&points[i].y<=dy[j]+L)
						v[i]=1,stack[++top]=i;
		bool flag=DFS(L,dpt+1);
		while(top!=bottom)
			v[stack[top--]]=0;
		if(flag)
			return true;
	}
	return false;
}
int Bisection()
{
	int l=0,r=0x3f3f3f3f;
	while(l+1<r)
	{
		int mid=l+r>>1;
		if( DFS(mid,0) )
			r=mid;
		else
			l=mid;
	}
	if( DFS(l,0) )
		return l;
	return r;
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		scanf("%d%d",&points[i].x,&points[i].y);
	cout<<Bisection()<<endl;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117596.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 电力通信网体系结构图_电力通信技术

    电力通信网体系结构图_电力通信技术电力通信网体系的分层可以从水平和垂直两个方面去理解:水平方向上可以划分两层,即骨干通信网、接入通信网;垂直方向上骨干网又可以分为传输网、数据网、支撑网。其中接入通信网可分为输变电通信网与配电通信网。一、骨干通信网1.1传输网:是由线路设施、传输设施等组成的为传送新消息业务提供所需传送承载能力的通道,它是通信网络的基础,它为整个通信网络上所承载的业务提供传输通道和平台。1.2

  • springboot集成日志

    springboot集成日志一、通过代码引入slf4j因为pom文件中已经通过父类引入了log4j查看中有直接进行引入即可。// 在类中引入,MyController是本类名 private static final Logger log = LoggerFactory.getLogger(MyController.class);下面直接使用即可。显示结果:默认情况下是info…

  • springEL表达式_赋值表达式的条件

    springEL表达式_赋值表达式的条件一、SpEL介绍二、SpEL用法1.在@Value注解中使用2.在XML配置中使用3.在代码中创建Expression对象三、SpEL原理1.解析器:ExpressionParser2.表达式:Expression3.上下文:EvaluationContext使用流程四、表达式语法1.基本表达式①字面量表达式②算数运算表达式③关系运算表达式④逻辑运算表达式⑤字符串连接及截取表达式⑥三目运算⑦Elivis表达式⑧正则表达式2.类相关表达式

  • 合并两个排序的单链表

    合并两个排序的单链表

  • Django(18)聚合函数

    Django(18)聚合函数前言orm模型中的聚合函数跟MySQL中的聚合函数作用是一致的,也有像Sum、Avg、Count、Max、Min,接下来我们逐个介绍聚合函数所有的聚合函数都是放在django.db.models

  • 初识LVS,lvs/dr和lvs/nat lvs/tun

    初识LVS,lvs/dr和lvs/nat lvs/tun

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号