首页 > 代码库 > BZOJ 4237: 稻草人
BZOJ 4237: 稻草人
4237: 稻草人
Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 661 Solved: 286
[Submit][Status][Discuss]
Description
JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数
Input
第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标
Output
输出一行一个正整数,代表遵从启示的田地的个数
Sample Input
4
0 0
2 2
3 4
4 3
0 0
2 2
3 4
4 3
Sample Output
3
HINT
所有满足要求的田地由下图所示:
1<=N<=2*10^5
0<=Xi<=10^9(1<=i<=N)
0<=Yi<=10^9(1<=i<=N)
Xi(1<=i<=N)互不相同。
Yi(1<=i<=N)互不相同。
Source
JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ
将y这一维分治一下,每次考虑一个平面,中间割开,下面每个点作为左下点时,上面可以和其配对的右上点的个数。
将所有点按x维排序,扫描线从右向左,上面维护一个单调上升的栈,下面维护一个单调下降的栈,每次拿到下面一个点时,先在下面的栈中二分出第一个y大于它的点,这个点的x坐标是不可逾越的。然后二分出上面栈中有多少个点在这个界限以左,就是这个左下点的合法配对数。
@Author: YouSiki
BZOJ 4237: 稻草人
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。