「BZOJ1818」[CQOI2010] 内部白点

2014年3月5日5,4551

Description

无限大正方形网格里有n个黑色的顶点,所有其他顶点都是白色的(网格的顶点即坐标为整数的点,又称整点)。每秒钟,所有内部白点同时变黑,直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。 内部白点的定义:一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点(即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点),且在竖直线的上边和下边各至少有一个黑点(即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点)。

Input

输入第一行包含一个整数n,即初始黑点个数。以下n行每行包含两个整数(x,y),即一个黑点的坐标。没有两个黑点的坐标相同,坐标的绝对值均不超过109。

Output

输出仅一行,包含黑点的最终数目。如果变色过程永不终止,输出-1。

Sample Input

4
0 2
2 0
-2 0
0 -2

Sample Output

5数据范围
36%的数据满足:n < = 500
64%的数据满足:n < = 30000
100%的数据满足:n < = 100000

题解

题目略难…想了一个多小时

首先证明不可能出现输出-1的情况:(其实黑点的增长只会发生在第一秒)
反设白点i在第一秒时由于某个方向(设为上方)没有黑点,就没有变成黑点,而在后来又成为了黑点。
此时在i点上方必有了黑点j,而j要成为黑点,j的上方必存在一个黑点,而那个黑点同时也在i的上方,
所以i一开始将成为黑点,矛盾!
那么我们只需求出有多少个整点满足上下左右都存在黑点。

然后先离散化横坐标,将横纵坐标相等的点看做竖线和横线,也就是分别按照点的x,y排序得到所有的线段

然后对所有线段进行排序,从下往上扫描,用树状数组维护区间和

如果碰到一条竖线下端点,将树状数组中其横坐标位置的值+1

碰到一条横线,就询问左端点到右端点并加入答案

如果碰到一条竖线上端点,将树状数组中其横坐标位置的值-1

想完这些我们可以发现,对于一条竖线段,我们可以把它的俩个端点分开和横线一起存入结构体,这样同时可以解决排序的问题

对线段进行排序时,如果y相同,上端点要在最前,下端点在最后

 

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
``` Recent comment authors
  Subscribe  
提醒
```
```

hhhhhhh