Hdu 5820 Lights(矩形中有多少个点)

传送门:Hdu 5820 Lights

---

题意:给你n个点,如果这是一条好的路径的话,任意两个点之间能到达且拐歪处一定有点,且走的距离为|x1-x2|+|y1-y2|

---

思路:我们对一个点找出它上下左右分别离它最近的是哪一个点,然后就组成了一个矩形,这要判断这个矩形里面是不是还有其它的点就可以了

#include<bits/stdc++.h>
using namespace std;
const int maxn=500100;
struct Point{
int x,y;
bool operator <(const Point &r) const{
return r.x==x ?  y<r.y : x<r.x;
    }
}a[maxn];
vector<int>row[50010+10];
int root[maxn],t[2*maxn],sz,b[maxn];

struct node{
int l,r,w;
}T[maxn*20];

void update(int &i,int l,int r,int num){
    T[++sz]=T[i],i=sz;
    T[i].w++;
if(l==r)
return ;
int mid=(l+r)>>1;
if(num<=mid)
        update(T[i].l,l,mid,num);
else
        update(T[i].r,mid+1,r,num);
}

int query(int x,int y,int l,int r,int num){
if(num==0)
return 0;
if(r==num)
return T[y].w-T[x].w;
int mid=(l+r)>>1;
if(num<=mid)
return query(T[x].l,T[y].l,l,mid,num);
else
return T[T[y].l].w-T[T[x].l].w+query(T[x].r,T[y].r,mid+1,r,num);
}

int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)
break;
for(int i=1;i<=50010;i++)
            row[i].clear(),row[i].push_back(0);
int tot=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1);
        root[0]=0,sz=0;
int nn=1;
        row[ a[1].y ].push_back( a[1].x );
for(int i=2;i<=n;i++){
if(a[i].x==a[nn].x&&a[i].y==a[nn].y)
continue;
else
                a[++nn].x=a[i].x,a[nn].y=a[i].y,row[ a[i].y ].push_back( a[i].x );
        }
for(int i=1;i<=50010;i++)
            row[i].push_back(50011);
int pre=0,cnt,flag=0;
for(int i=1;i<=nn;i++){
for(int j=pre+1;j<=a[i].x;j++)
                root[j]=root[j-1];
            pre=a[i].x,cnt=0;
            update(root[pre],1,50010,a[i].y);
while(i<nn&&a[i+1].x==a[i].x)
                i++,update(root[pre],1,50010,a[i].y);
        }
for(int i=pre+1;i<=50010;i++)
            root[i]=root[i-1];
for(int i=1;i<=nn;i++){
            cnt=0,pre=a[i].x;
            b[0]=0,b[++cnt]=a[i].y;
while(i<nn&&a[i+1].x==a[i].x)
                i++,b[++cnt]=a[i].y;
            b[cnt+1]=50011;
for(int j=1;j<=cnt;j++){    //处理这一列
int id=lower_bound(row[ b[j] ].begin(), row[ b[j] ].end(),pre)-row[ b[j] ].begin();
int l=row[ b[j] ][ id-1 ],r=row[ b[j] ][ id+1 ]-1;
int num=query(root[l],root[r],1,50010,b[j+1]-1)-query(root[l],root[r],1,50010,b[j-1]);
if(num>1){
                    flag=1;
break;
                }
            }
if(flag==1)
break;
        }
if(flag==0)
printf("YES\n");
else
printf("NO\n");
    }
return 0;
}