BZOJ 1941: [Sdoi2010]Hide and Seek(k-d Tree)
2018-06-27 10:06:37来源:未知 阅读 ()
Submit: 1712 Solved: 932
[Submit][Status][Discuss]
Description
小猪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的问题。
Input
第一行输入一个整数N 第2~N+1行,每行两个整数X,Y,表示第i个地点的坐标
Output
一个整数,为距离差的最小值。
Sample Input
0 0
1 0
0 1
1 1
Sample Output
HINT
对于30%的数据,N<=1000 对于100%的数据,N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2
Source
SDOI2010 第二轮Day 1
#include<cstdio> #include<algorithm> //#define int long long //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) using namespace std; const int MAXN = 200001, INF = 1e9 + 10; char buf[1 << 21], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N; int WD = 0, cur = 0, root; #define ls(k) T[k].ls #define rs(k) T[k].rs struct Point { int x[2]; bool operator < (const Point &rhs) const { return x[WD] < rhs.x[WD]; } }p[MAXN]; struct Node { int mi[2], mx[2], ls, rs; Point tp; }T[MAXN]; int NewNode() { return ++cur; } void update(int k) { for(int i = 0; i <= 1; i++) { T[k].mi[i] = T[k].mx[i] = T[k].tp.x[i]; if(ls(k)) T[k].mi[i] = min(T[ls(k)].mi[i], T[k].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]); if(rs(k)) T[k].mi[i] = min(T[rs(k)].mi[i], T[k].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]); } } int Build(int l, int r, int wd) { if(l > r) return 0; int k = NewNode(), mid = l + r >> 1; WD = wd; nth_element(p + l, p + mid, p + r + 1); T[k].tp = p[mid]; T[k].ls = Build(l, mid - 1, wd ^ 1); T[k].rs = Build(mid + 1, r, wd ^ 1); update(k); return k; } int Ans; int dis(Point a, Point b) {//曼哈顿距离 return abs(a.x[0] - b.x[0]) + abs(a.x[1] - b.x[1]); } int GetMinDis(Point a, Node b) {// 点到矩阵的最小曼哈顿距离 int rt = 0; for(int i = 0; i <= 1; i++) rt += max(0, a.x[i] - b.mx[i]) + max(0, b.mi[i] - a.x[i]); return rt; } int GetMaxDis(Point a, Node b) {//最大曼哈顿距离 int rt = 0; for(int i = 0; i <= 1; i++) rt += max( max(0, a.x[i] - b.mi[i]), max(0, b.mx[i] - a.x[i]) ); //rt += max(abs(a.x[i] - b.mi[i]), abs(a.x[i] - b.mx[i])); return rt; } int QueryMax(int k, Point a) { Ans = max(Ans, dis(a, T[k].tp)); int disl = -INF, disr = -INF; if(ls(k)) disl = GetMaxDis(a, T[ls(k)]); if(rs(k)) disr = GetMaxDis(a, T[rs(k)]); if(disl > disr) { if(disl > Ans) Ans = QueryMax(ls(k), a); if(disr > Ans) Ans = QueryMax(rs(k), a); } else { if(disr > Ans) Ans = QueryMax(rs(k), a); if(disl > Ans) Ans = QueryMax(ls(k), a); } } int QueryMin(int k, Point a) { int tmp = dis(a, T[k].tp); if(tmp) Ans = min(Ans, tmp); int disl = INF, disr = INF; if(ls(k)) disl = GetMinDis(a, T[ls(k)]); if(rs(k)) disr = GetMinDis(a, T[rs(k)]); if(disl < disr) { if(disl < Ans) Ans = QueryMin(ls(k), a); if(disr < Ans) Ans = QueryMin(rs(k), a); } else { if(disr < Ans) Ans = QueryMin(rs(k), a); if(disl < Ans) Ans = QueryMin(ls(k), a); } } main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); for(int i = 1; i <= N; i++) p[i].x[0] = read(), p[i].x[1] = read(); root = Build(1, N, 0); int ans = INF, ans1 = 0, ans2 = 0; for(int i = 1; i <= N; i++) { ans1 = 0, ans2 = 0; Ans = -INF; QueryMax(root, p[i]); ans1 = Ans; Ans = INF; QueryMin(root, p[i]); ans2 = Ans; // printf("%d %d\n", ans1, ans2); ans = min(ans, ans1 - ans2); } printf("%d", ans); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:OJ:又一道考察多态的题目
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash