「BZOJ1818」[CQOI2010] 内部白点
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
0 2
2 0
-2 0
0 -2
Sample Output
5数据范围
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000
题解
题目略难…想了一个多小时
首先证明不可能出现输出-1的情况：（其实黑点的增长只会发生在第一秒）
反设白点i在第一秒时由于某个方向（设为上方）没有黑点，就没有变成黑点，而在后来又成为了黑点。
此时在i点上方必有了黑点j，而j要成为黑点，j的上方必存在一个黑点，而那个黑点同时也在i的上方，
所以i一开始将成为黑点，矛盾！
那么我们只需求出有多少个整点满足上下左右都存在黑点。
然后先离散化横坐标,将横纵坐标相等的点看做竖线和横线，也就是分别按照点的x,y排序得到所有的线段
然后对所有线段进行排序,从下往上扫描,用树状数组维护区间和
如果碰到一条竖线下端点,将树状数组中其横坐标位置的值+1
碰到一条横线,就询问左端点到右端点并加入答案
如果碰到一条竖线上端点,将树状数组中其横坐标位置的值-1
想完这些我们可以发现,对于一条竖线段,我们可以把它的俩个端点分开和横线一起存入结构体,这样同时可以解决排序的问题
对线段进行排序时,如果y相同,上端点要在最前,下端点在最后
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,cnt,ans,hash[100001],tr[100001]; struct point{int x,y;}a[100001]; struct seg{int k,x,y,r;}s[1000001]; inline bool cmp1(point a,point b) {if(a.x==b.x){return a.y<b.y;}return a.x<b.x;} inline bool cmp2(point a,point b) {if(a.y==b.y){return a.x<b.x;}return a.y<b.y;} inline bool cmp3(seg a,seg b) { if(a.y==b.y)return a.k<b.k; return a.y<b.y; } int find(int x) { int l=1,r=n,mid; while(l<=r) { int mid=(l+r)>>1; if(hash[mid]<x)l=mid+1; else if(hash[mid]>x)r=mid-1; else return mid; } } void insert(int k,int l,int r,int t)//0横线,1竖线 { if(!k){s[++cnt].x=find(l);s[cnt].r=find(r);s[cnt].y=t;} else{ s[++cnt].x=find(t);s[cnt].y=l;s[cnt].k=1; s[++cnt].x=find(t);s[cnt].y=r;s[cnt].k=-1; } } void build() { sort(a+1,a+n+1,cmp1); for(int i=2;i<=n;i++) if(a[i].x==a[i-1].x) insert(1,a[i-1].y,a[i].y,a[i].x); sort(a+1,a+n+1,cmp2); for(int i=2;i<=n;i++) if(a[i].y==a[i-1].y) insert(0,a[i-1].x,a[i].x,a[i].y); } int lowbit(int x){return x&(-x);} void update(int x,int y) { while(x<=n) { tr[x]+=y; x+=lowbit(x); } } int ask(int x) { int s=0; while(x) { s+=tr[x]; x-=lowbit(x); } return s; } void work() { for(int i=1;i<=cnt;i++) { if(!s[i].k)ans+=ask(s[i].r-1)-ask(s[i].x); else update(s[i].x,s[i].k); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); hash[i]=a[i].x; } sort(hash+1,hash+n+1); build(); sort(s+1,s+cnt+1,cmp3); work(); printf("%d",ans+n); return 0; } |
hhhhhhh