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)


相关推荐

  • centos安装supervisor详细教程

    centos安装supervisor详细教程centos安装supervisor详细教程

  • 需求分析报告应该包含哪些部分_2020最新抖音用户画像分析报告:粉丝都有哪些特点和需求?…[通俗易懂]

    需求分析报告应该包含哪些部分_2020最新抖音用户画像分析报告:粉丝都有哪些特点和需求?…[通俗易懂]本文相关:抖音用户画像分析、抖音用户画像报告、2020最新抖音用户画像分析等不管是做抖音运营还是抖音直播,了解粉丝,了解用户的需求是非常重要的!做任何事情,对症下药你才能事半功倍!比如你的粉丝想要梨子,你却给他了一个苹果,你的粉丝大部分都是分布在三线开外的城市,你却总给他们推荐昂贵的鸡肋产品!这就是没有提前了解抖音用户画像的结果!接下来,我就给你分析一下最新的抖音用户画像报告!让你运营起…

  • MySQL自动化运维平台建设

    MySQL自动化运维平台建设MySQL自动化运维工具Inception一、Inception简介Inception是集审核、执行、回滚于一体的一个自动化运维系统,它是根据MySQL代码修改过来的,用它可以很明确的,详细的,准确的审核MySQL的SQL语句,它的工作模式和MySQL完全相同,可以直接使用MySQL客户端来连接,但不需要验证权限,它相对应用程序(上层审核流程系统等)而言,是一个服务器,在连接…

  • python 去掉文件后缀名,python 删除后缀名文件

    python 去掉文件后缀名,python 删除后缀名文件Note:print语句供test用#!/usr/bin/pythonimportos,re,time,sysimportos.pathimportstringfilter_dir=”/home/fengnazh/splittest/files/”filterfile_list=os.listdir(filter_dir)printfilterfile_listfile_i…

  • long转string mybatis_Long转String总结

    long转string mybatis_Long转String总结平时很少会使用到,今天用到了,做一个小总结。1.程序packagecom.jun.webpro.common.units;/***列举了两种比较常见的Long转String的方法*通过测试,发现如果传入null,则第一种方式报错;第二种方式打印出null字符串*/publicclassLongToStringUtils{/***使用Long的方法*@paramvalueLong…

  • 孰能生巧

    孰能生巧

发表回复

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

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