【HDOJ 5820】Lights（扫描线+线段树）

Lights

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 356 Accepted Submission(s): 33

Problem DescriptionToday is April 1st, 2100. Now Guangzhou is a very very big city. Since the number of traffic accidents increased last month, the mayor asked Mr. Chopsticks to investigate the traffic condition of the city.

After studying the map of Guangzhou for a while, Mr. Chopsticks has some ideas. Guangzhou can be considered as a rectangular grid with 50000 horizontal streets running west-east (labeled with y-coordinates from 1 to 50000) and 50000 vertical streets running north-south (labeled with x-coordinates from 1 to 50000). All streets are two-way streets. A crossroad is an intersection of a horizontal street and a vertical street, so a crossroad can be represented by (x, y), where x and y are coordinates of the horizontal street and vertical street respectively. Since there are too many streets, traffic lights are not placed at all crossroads. Given two crossroads (x1, y1) and (x2, y2), a path between these two crossroads is said to be good if the length of the path is |x1 – x2| + |y1 – y2| and there exist a traffic light at each turn of this path. Of course, a path must be along the streets, and a turn can only be at a crossroad.

Now given locations of all traffic lights in Guangzhou, Mr. Chopsticks wants to check whether there exists at least one good path between every pair of traffic lights. As Mr. Chopsticks is busy in preparing ACMICPC 2100, he asks you for help.

InputThe input contains multiple test cases. Each case begins with an integer N (1 <= N <= 500000), indicating the number of traffic lights. The following N lines each contain two integers x and y (1 <= x, y <= 50000), indicating a location of a traffic light. There may be multiple traffic lights at the same location.

N = 0 indicates the end of the input.

OutputFor each case, output “YES” if there exists at least one good path between every pair of traffic lights; otherwise output “NO”.

Sample Input

Sample Output

NO
YES

AuthorSYSU

Source 2016 Multi-University Training Contest 7

题目大意：

定义在二维平面内，每个平行与x轴和y轴的直线均为以条路。
这些路之间会有很多交叉点。

给出n个坐标，表示在 (x,y) 处有红绿灯。（ x,y 均为正整数）

从 i 红绿灯到 j 红绿灯，可行的要求是至少存在一条从i灯到j灯的长为两点间曼哈顿距离的路，满足路径上每个拐点都有红绿灯。

譬如
点 (1,1) 到点 (2,2) 可行，必须要 (1,2) 和 (2,1) 两点中至少一个点有灯。

考虑将点按纵坐标从大到小，横坐标从小到大排序。
即遍历点从上到下，从左到右的顺序。

这样当遍历到点 (x,y) 时，保证了纵坐标 >y 的点，以及 (x,y) 点左边的点都已经被遍历过。
并且此时未跳出，保证这些点之间是相互可达的。那么只要看点 (x,y) 能否与之前的所有点相互到达即可。

设点(x,y)左边的最近点为 (xl,y) ，右边最近点为 (xr,y) ，上边最近点为 (x,yu)

不存在就弄成边界就好。

那么对于之前的点 (x′,y′) ，有如下几种情况
x′≤xl 那么一定可以经过 (xl,y) 到达 (x,y)
y′≥yu 那么一定可以经过 (xu,y) 到达 (x,y)
x′≥xr 如果可达 (xr,y) ，那么就能到 (x,y)

对于前两种，当前时刻是保证正确的。
第三种，其实是一种传递的关系。如果对于 (x,y) 右边的点，一直是这样的话，到达最右边时， (xr,y) 会变成边界，如果不满足第二个条件，也会被pass掉。

那么除此之外的点，其实就是由 (x,y) (xl,y) (xr,y) (x,yu) 构成的一个矩形内部。

如果这里有点，那么没有任何办法到达 (x,y) ，上面的第三种情况，其实就是在这里被干掉的。

那么问题就转换为，排序后，从上到下从左到右一次遍历。
对于每个点，找到左上右最近的点，如果构成的矩形内部有点，print”NO”
如果都没有 print”YES”

这里我是用线段树统计横坐标在区间[xl+1,xr-1]中，纵坐标的最小值
然后与 yu 比较，如果比 yu 小，说明左右最近点内，有在上最近点下的点，翻译来其实就是有被包含在矩形内的点。

然后就没了

PS：开始写傻了，把x,y想做行列的那种。。然后就用了鬼畜的方式把坐标转换成行列—–

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#define LL long long
#define Pr pair<int,int>
#define fread(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int mod = 1000000007;

int mx[55555];
int bit[4*55555];
Pr pt[555555];

bool cmp(Pr a,Pr b)
{
return a.first == b.first? a.second < b.second: a.first > b.first;
}

void init(int root,int l,int r)
{
    bit[root] = -1;

if(l == r)
    {
return;
    }

int mid = (l+r)>>1;

    init(root<<1,l,mid);
    init(root<<1|1,mid+1,r);
}

void Add(int root,int l,int r,int ll,int rr,int x)
{
//printf("%d %d\n",l,r);
    bit[root] = x;
if(l == ll && r == rr)
    {
return;
    }

int mid = (l+r)>>1;

if(mid >= rr)
    {
        Add(root<<1,l,mid,ll,rr,x);
    }
else if(mid+1 <= ll)
    {
        Add(root<<1|1,mid+1,r,ll,rr,x);
    }
else
    {
        Add(root<<1,l,mid,ll,mid,x);
        Add(root<<1|1,mid+1,r,mid+1,rr,x);
    }
}

int Search(int root,int l,int r,int ll,int rr)
{
//printf("%d %d\n",l,r);
//bit[root] = max(bit[root],x);
if(ll > rr) return -1;
if(l == ll && r == rr)
    {
return bit[root];
    }

int mid = (l+r)>>1;

if(mid >= rr)
    {
return Search(root<<1,l,mid,ll,rr);
    }
else if(mid+1 <= ll)
    {
return Search(root<<1|1,mid+1,r,ll,rr);
    }
else
    {
return max(Search(root<<1,l,mid,ll,mid),Search(root<<1|1,mid+1,r,mid+1,rr));
    }
}

int main()
{

int n;

int l,r;
    l = 0;
    r = 500001;

while(~scanf("%d",&n) && n)
    {
        l = 0;
        r = 0;
int col = 0;
for(int i = 0; i < n; ++i)
        {
scanf("%d%d",&pt[i].second,&pt[i].first);
            r = max(r,pt[i].second);
            col = max(col,pt[i].first);
        }
        r++;
        col++;

int root = 1;
        init(root,l,r);
        sort(pt,pt+n,cmp);
memset(mx,-1,sizeof(mx));
bool f = 1;
int st = 0;

        pt[0].first = col-pt[0].first;
for(int i = 0; i < n; ++i)
        {
int tmp;
if(i < n-1) pt[i+1].first = col-pt[i+1].first;
//printf("%d %d %d\n",pt[i].first,pt[i].second,f);
if((i == 0 || pt[i].first != pt[i-1].first) && (i == n-1 || pt[i].first != pt[i+1].first))
            {
while(st < i)
                {
                    Add(root,l,r,pt[st].second,pt[st].second,pt[st].first);
                    st++;
                }
                tmp = Search(root,l,r,l+1,r-1);
            }
else if(i == 0 || pt[i].first != pt[i-1].first)
            {
while(st < i)
                {
                    Add(root,l,r,pt[st].second,pt[st].second,pt[st].first);
                    st++;
                }
//printf("*%d %d\n",l+1,pt[i+1].second-1);
                tmp = Search(root,l,r,l+1,pt[i+1].second-1);
            }
else if(i == n-1 || pt[i].first != pt[i+1].first)
            {
                tmp = Search(root,l,r,pt[i-1].second+1,r-1);
            }
else
            {
                tmp = Search(root,l,r,pt[i-1].second+1,pt[i+1].second-1);
            }

//printf("%d %d %d\n",pt[i].second,mx[pt[i].second],tmp);
if(tmp > mx[pt[i].second])
            {
                f = 0;
break;
            }

            mx[pt[i].second] = pt[i].first;
        }

puts(f? "YES": "NO");
    }

return 0;
}

秒客网

【HDOJ 5820】Lights（扫描线+线段树）

Lights

相关文章