首页 > itarticle > 「bzoj1941」hide and seek

「bzoj1941」hide and seek

admin 11月 13, 2020 0

来源和评测点

Sdoi2010
Bzoj1941

题目

「题目大意」
小猪iPig在PKU刚上完了无聊的猪性代数课，
天资聪慧的iPig被这门对他来说无比简单的课弄得灰常寂寞。
为了消除寂寞感，他决定和他的好朋友giPi（鸡皮）玩一个更加寂寞的游戏—捉迷藏。
但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，
于是，他们决定玩寂寞无比的螃蟹版捉迷藏，
顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。
一番寂寞的剪刀石头布后，他们决定iPig去捉giPi。
由于他们都很熟悉PKU的地形了，所以giPi只会躲在PKU内n个隐秘地点，
显然iPig也只会在那n个地点内找giPi。
游戏一开始，他们选定一个地点，iPig保持不动，
然后giPi用30秒的时间逃离现场（显然，giPi不会呆在原地）。
然后iPig会随机地去找giPi，直到找到为止。
由于iPig很懒，所以他到总是走最短的路径，而且，他选择起始点不是随便选的，
他想找一个地点，使得该地点到最远的地点和最近的地点的距离差最小。
iPig现在想知道这个距离差最小是多少。
由于iPig现在手上没有电脑，所以不能编程解决这个如此简单的问题，
所以他马上打了个电话，要求你帮他解决这个问题。
iPig告诉了你PKU的n个隐秘地点的坐标，请你编程求出iPig的问题。
「输入格式」
第一行输入一个整数N 第2~N+1行，每行两个整数X，Y，表示第i个地点的坐标
「输出格式」
一个整数，为距离差的最小值。
「输入样例」
4
0 0
1 0
0 1
1 1
「输出样例」
1

刷题记录

30min
1AC

分析

kdtree
暴力枚举即可

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 

//*******************头文件*******************

#include<cstring>
#include<algorithm>
using namespace std;
int (int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=510000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct nod
{
	int d[2];//自己
	int son[2];//左右区间
	int mi[2],mx[2];//管理区间
	nod()
	{
		son[0]=son[1]=0;
	}
}p[MAXN];
int root;
//*******************kdtree*******************
int D;
bool cmp(nod a,nod b)
{
	return (a.d[D]<b.d[D]) or (a.d[D]==b.d[D] and a.d[1-D]<b.d[1-D]);
}
void update(int f,int x)
{
	p[f].mi[0]=mymin(p[f].mi[0],p[x].mi[0]);p[f].mx[0]=mymax(p[f].mx[0],p[x].mx[0]);
	p[f].mi[1]=mymin(p[f].mi[1],p[x].mi[1]);p[f].mx[1]=mymax(p[f].mx[1],p[x].mx[1]);
}
int getdis(int t,int x,int y,int op)//最近
{
	if(op==0)
	{
		int ans=0;//在内部
		if(x<p[t].mi[0]) ans+=p[t].mi[0]-x;//左
		if(p[t].mx[0]<x) ans+=x-p[t].mx[0];//右
		if(p[t].mx[1]<y) ans+=y-p[t].mx[1];//上
		if(y<p[t].mi[1]) ans+=p[t].mi[1]-y;//下
		return ans;
	}
	else
	{
		return mymax(myabs(x-p[t].mx[0]),myabs(x-p[t].mi[0]))+
		mymax(myabs(y-p[t].mx[1]),myabs(y-p[t].mi[1]));
	}
	
}
//*******************实现*******************
int build(int l,int r,int d)
{
	if(l>r) return 0;
	
	int mid=(l+r)/2;D=d;
	nth_element(p+l,p+mid,p+r+1,cmp);//尽量平衡
	
	p[mid].mi[0]=p[mid].mx[0]=p[mid].d[0];
	p[mid].mi[1]=p[mid].mx[1]=p[mid].d[1];
	if(l<=mid-1) p[mid].son[0]=build(l,mid-1,1-d),update(mid,p[mid].son[0]);
	if(mid+1<=r) p[mid].son[1]=build(mid+1,r,1-d),update(mid,p[mid].son[1]);
	return mid;
}
int ans;
void ask(int now,int x,int y,int op)
{
	int dis=myabs(p[now].d[0]-x)+myabs(p[now].d[1]-y);//自身
	if(dis!=0)
	{
		if(op==0) ans=mymin(ans,dis);
		else ans=mymax(ans,dis);
	}
	
	int f[2],lc=p[now].son[0],rc=p[now].son[1];
	
	if(op==0)
	{
		f[0]=lc?getdis(lc,x,y,op):INF;
		f[1]=rc?getdis(rc,x,y,op):INF;
		bool tmp=(f[1]<=f[0]);
		if(f[tmp]<ans) ask(p[now].son[tmp],x,y,op);
		if(f[1-tmp]<ans) ask(p[now].son[1-tmp],x,y,op);
	}
	else
	{
		f[0]=lc?getdis(lc,x,y,op):0;
		f[1]=rc?getdis(rc,x,y,op):0;
		bool tmp=(f[1]>=f[0]);
		if(f[tmp]>ans) ask(p[now].son[tmp],x,y,op);
		if(f[1-tmp]>ans) ask(p[now].son[1-tmp],x,y,op);
	}
}
//*******************主函数*******************
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].d[0],&p[i].d[1]);
	root=build(1,n,0);
	int mi=INF;
	for(int i=1;i<=n;i++)
	{
		ans=0;
		ask(root,p[i].d[0],p[i].d[1],1);
		int t=ans;ans=INF;
		ask(root,p[i].d[0],p[i].d[1],0);
		mi=mymin(mi,t-ans);
	}
	printf("%d",mi);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能