hiho一下第154周《穿越禁区》题目分析

6
0

《穿越禁区》题目分析

题目大意：给定一个矩形区域，其中有一些圆形雷区。问是否存在一条从左边界移动到右边界的路线，并且中途不经过任何雷区(也不能接触雷区边缘)。起点可选在左边界任意一点，终点可选在右边界任意一点。

例如下图中，上面的情况就没有办法穿越，下面的情况则可以穿越。

week154-1

我们人脑会有一个很直观的判断，如果雷区没有把左边界和右边界分隔开的话，那么就一定有一条穿越的路线；否则如果左右边界被雷区隔开，那么就一定不存在穿越路线。

week154-2

问题在于如何把我们脑内直观的判断转化成程序能进行的确定的判断。通过分析我们可以发现：

  1. 如果两个圆相切或者相交，那么它们的雷区会合并在一起
  2. 若干个圆连续相切或者相交，会形成一片连通的雷区
  3. 如果一片连通的雷区同时与上下边界相交或相切，那么这片雷区就会把左右边界分割开来；反之亦然

week154-3

于是我们可以把原本的几何问题转化成一个图论问题。我们把每一个圆看作一个顶点，同时把上边界看作起点，下边界看作终点。如果两个圆或者圆与边界之间是相交或者相切的，我们就在代表两者的顶点之间连一条边。最后如果存在一条起点到终点的路径，那么就不存在从左到右的穿越路线；反之如果不存在起点到终点的路径，就存在从左到右的穿越路线。

所以第一步我们要做的是建图。这个图一共有N+2个顶点。每对顶点之间我们都要判断是否有边相连，也就是判断圆与圆以及圆与边界是否相交或相切。

这是个简单的计算几何问题。对于圆与圆来说，只需要判断圆心距和半径之和的大小关系；对于圆与边界来说，需要判断圆心到边界的距离和半径的关系，由于边界是平行于X轴的，所以只需要比较Y坐标就能求出圆心到边界的距离。

由于有(N+2)(N+1)/2条边要判断，第一步的复杂度是O(N^2)。

第二步是要判断是否有从起点到终点的路径。这一步我们可以用宽搜、深搜或者并查集来实现，复杂度也是O(N^2)的。

9 answer(s)

0

Union中在合并两个区域的时候用:father[i] = j;就TLE，用father[j] = i;就能AC，求指教，不懂为什么。。理论上谁去合并谁不都一样吗？不知道什么样的例子通不过。

#include<iostream>
#include<math.h>
using namespace std;
int T, W, H, N;
int x[1000003], y[1000003], r[1000003], father[1000003];

float dis(int i, int j){
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}

void Union(int i, int j){
    while (father[i] != i) i = father[i];
    while (father[j] != j) j = father[j];
    father[i] = j;
}
int findfather(int x){
    int i = x,j;
    while (father[i] != i) i = father[i];
    return i;
}
int main(){
    cin >> T;
    while (T--){
        cin >> W >> H >> N;
        for (int i = 0; i<N; ++i){
            cin >> x[i] >> y[i] >> r[i];
            father[i] = i;
        }
        father[N] = N; father[N + 1] = N + 1;
        for (int i = 0; i<N; ++i){
            for (int j = i + 1; j<N; ++j){
                if (dis(i, j) <= r[i] + r[j])
                    Union(i, j);
            }
            if (y[i] <= r[i]) Union(i, N);
            if (y[i] >= H - r[i]) Union(i, N + 1);
        }
        if (findfather(N)==findfather(N+1)) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}
0 
#include <iostream>

#define ll long long
using namespace std;
struct node
{
ll x;
ll y;
ll r;
}p[1002];

int parent[1005];

bool judge(node a, node b)
{
ll x = (a.x-b.x)*(a.x-b.x);
ll y = (a.y-b.y)*(a.y-b.y);
ll z = (a.r+b.r)*(a.r+b.r);
if(x+y<=z)
    return true;
else
    return false;
}

int find(int a)
{
int b = a;
while(parent[b]!=b)
{
    parent[b] = parent[parent[b]];
    b = parent[b];
}
return b;
}


void unioon(int a, int b)
{
if(find(a)!=find(b));
parent[find(b)] = find(a);
}

int main()
{
int t;

scanf("%d",&t);

while(t--)
{
    int w,h,n;
    scanf("%d %d %d",&w,&h,&n);

    for(int i=0; i<n;i++)
    {
        scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].r);
        parent[i] = i;
    }

    parent[1002] = 1002; //下边界
    parent[1001] = 1001;//上边界

    for(int i=0; i<n;i++)
    {
        if(p[i].y<=p[i].r)unioon(1001,i);
        if((h-p[i].y)<=p[i].r)unioon(i,1002);
    }
    for(int i=0; i<n;i++)
        for(int j=i+1; j<n; j++)
            if(judge(p[i],p[j]))unioon(i,j);

    if(find(1001) == find(1002))printf("NO\n");    //把find(1001)替换成1001就无法通过
    else
        printf("YES\n");
}
return 0;
}

问一下为什么上面这个代码把find(1001)替换成1001就无法通过了，find(1001)不应该是恒等于1001的么

0

一直70/100,总是wrong answer,不知道什么原因。。。

0

提交出现弹出框 ERROR json怎么办

  • Ucloud一台物理机挂了，我们的一台评测虚拟机在上面 orz...

  • 新部署了一台，现在OK了。

  • 添加评论
  • ✖reply
0 
超时了。。。

import java.util.*;

public class Main {

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int t = 0; t < T; t++){
        int W = sc.nextInt();
        int H = sc.nextInt();
        int N = sc.nextInt();
        Circle[] circles = new Circle[N];
        for(int i = 0; i < N; i++){
            Circle circle = new Circle(sc.nextInt(), sc.nextInt(), sc.nextInt());
            circles[i] = circle;
        }

        int[][] graph = new int[N + 2][N + 2];

        for(int i = 0; i < N; i++){
            Circle temp = circles[i];
            if(fuckUp(temp, W, H)){
                graph[i][N] = 1;
                graph[N][i] = 1;
            }
            if(fuckDown(temp, W, H)){
                graph[i][N + 1] = 1;
                graph[N + 1][i] = 1;
            }
            for(int j = i + 1; j < N; j++){
                if(hasIntersection(circles[i], circles[j])){
                    graph[i][j] = 1;
                    graph[j][i] = 1;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < N + 2; i++){
            if(graph[i][N] == 1){
                queue.add(i);
            }
        }
        boolean hasFind = false;
        boolean[] visited = new boolean[N + 2];
        while(!queue.isEmpty()){
            int temp = queue.poll();
            visited[temp] = true;
            if(temp == N + 1){
                System.out.println("NO");
                hasFind = true;
                break;
            }
            for(int i = 0; i < N + 2; i++){
                if(!visited[i] && graph[i][temp] == 1){
                    queue.add(i);
                }
            }
        }
        if(!hasFind)
            System.out.println("YES");
    }
}

private static boolean hasIntersection(Circle circle1, Circle circle2) {
    int distance = (circle1.getX() - circle2.getX())*(circle1.getX() - circle2.getX()) +
            (circle1.getY() - circle2.getY())*(circle1.getY() - circle2.getY());
    if(distance > (circle1.getR() + circle2.getR())*(circle1.getR() + circle2.getR())){
        return false;
    }else{
        return true;
    }
}

private static boolean fuckDown(Circle temp, int w, int h) {
    if(temp.getY() - temp.getR() > 0)
        return false;
    else
        return true;
}

private static boolean fuckUp(Circle temp, int w, int h) {
    if(temp.getY() + temp.getR() < h)
        return false;
    else
        return true;
}

static class Circle{
    int x;
    int y;
    int r;
    public Circle(int x, int y, int r){
        this.x = x;
        this.y = y;
        this.r = r;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getR() {
        return r;
    }
    public void setR(int r) {
        this.r = r;
    }
}

}

0

nlogn做法有吗

  • 不知道。 如果雷区是大小相同的正方形是有nlogn做法的。

  • 添加评论
  • ✖reply
0

70/100到底是什么测试数据？总是出错。

  • 你可以PO一下你的代码，注意参考置顶帖子里的方法

  • 对不起，犯了个愚蠢的错误。数字越界了，应该用long long。谢谢：）

  • 添加评论
  • ✖reply
1

第二个用例有点疑问 对于这两个圆形5 1 1 6 3 1 在矩形区域（10，4）中，当行x=5时 这时不管y是几0,1,2,3都在圆形覆盖范围内呀。

  • 这题路线并不要求是直线，也不要求是整点，可以随便拐随便走。

  • 添加评论
  • ✖reply
1

楼上说的很好——๑乛◡乛๑

这个题目就是要拦截路径。要使第一行到第n行中，几个雷达将水平方向所有缝隙都切断了。我们可以这样想——如果两个雷达的范围有交集（哪怕是一点），那么它们可以看作一个整体，以他们为整体的雷达区能探测的范围就是两个雷达范围的交集。怎么合并？并查集呗！ 合并后，会出现几个雷达区，他们互不相交。当一个雷达区能覆盖左右边界时，就能拦截路径了。

write answer 切换为英文 切换为中文

转发分享

▲