Walls

Solution Approach

Visibility Graph

The shortest path between two points amidst polygonal obstacles follows the edges of the visibility graph:

• Nodes: All polygon vertices, plus the source and destination.

• Edges: Two nodes are connected if the line segment between them does not pass through the interior of any polygon (touching a boundary is allowed).

• Weights: Euclidean distances.

Algorithm

For each query (source-destination pair):

1. Build the visibility graph including all polygon vertices and the two query points.

2. Run Dijkstra's algorithm to find the shortest path from source to destination.

Visibility Check

Two points are mutually visible if the segment connecting them does not properly intersect any polygon edge. We check each polygon's edges for proper intersection with the query segment.

A proper intersection of segments $AB$ and $CD$ occurs when $A$ and $B$ lie on strictly opposite sides of line $CD$, and $C$ and $D$ lie on strictly opposite sides of line $AB$. This is determined by the signs of cross products.

C++ Solution

#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const double EPS = 1e-9;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator-(const Point& o) const { return {x - o.x, y - o.y}; }
    Point operator+(const Point& o) const { return {x + o.x, y + o.y}; }
    double cross(const Point& o) const { return x * o.y - y * o.x; }
    double dot(const Point& o) const { return x * o.x + y * o.y; }
    double norm() const { return sqrt(x * x + y * y); }
};

double dist(Point a, Point b) { return (a - b).norm(); }

// Check if segments AB and CD intersect properly (cross in their interiors)
bool segmentsIntersectProperly(Point a, Point b, Point c, Point d) {
    double d1 = (b - a).cross(c - a);
    double d2 = (b - a).cross(d - a);
    double d3 = (d - c).cross(a - c);
    double d4 = (d - c).cross(b - c);

    if (((d1 > EPS && d2 < -EPS) || (d1 < -EPS && d2 > EPS)) &&
        ((d3 > EPS && d4 < -EPS) || (d3 < -EPS && d4 > EPS)))
        return true;
    return false;
}

// Check if segment PQ is blocked by any edge of a polygon
bool segmentBlockedByPolygon(Point p, Point q, vector<Point>& poly) {
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        Point a = poly[i], b = poly[(i + 1) % n];
        if (segmentsIntersectProperly(p, q, a, b))
            return true;
    }
    return false;
}

int main() {
    int N;
    scanf("%d", &N);

    vector<vector<Point>> polygons(N);
    vector<Point> allPoints;

    for (int i = 0; i < N; i++) {
        int m;
        scanf("%d", &m);
        polygons[i].resize(m);
        for (int j = 0; j < m; j++) {
            scanf("%lf %lf", &polygons[i][j].x, &polygons[i][j].y);
            allPoints.push_back(polygons[i][j]);
        }
    }

    int Q;
    scanf("%d", &Q);

    while (Q--) {
        Point src, dst;
        scanf("%lf %lf %lf %lf", &src.x, &src.y, &dst.x, &dst.y);

        // Build visibility graph: polygon vertices + src + dst
        vector<Point> nodes = allPoints;
        int srcIdx = nodes.size();
        nodes.push_back(src);
        int dstIdx = nodes.size();
        nodes.push_back(dst);

        int V = nodes.size();
        vector<vector<pair<int, double>>> adj(V);

        for (int i = 0; i < V; i++) {
            for (int j = i + 1; j < V; j++) {
                bool blocked = false;
                for (int k = 0; k < N; k++) {
                    if (segmentBlockedByPolygon(nodes[i], nodes[j], polygons[k])) {
                        blocked = true;
                        break;
                    }
                }
                if (!blocked) {
                    double d = dist(nodes[i], nodes[j]);
                    adj[i].push_back({j, d});
                    adj[j].push_back({i, d});
                }
            }
        }

        // Dijkstra from srcIdx to dstIdx
        vector<double> dists(V, 1e18);
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
        dists[srcIdx] = 0;
        pq.push({0, srcIdx});

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dists[u] + EPS) continue;
            for (auto [v, w] : adj[u]) {
                if (dists[u] + w < dists[v] - EPS) {
                    dists[v] = dists[u] + w;
                    pq.push({dists[v], v});
                }
            }
        }

        printf("%.2f\n", dists[dstIdx]);
    }

    return 0;
}

Correctness

The visibility graph approach is a well-known method for shortest paths among polygonal obstacles. The key properties ensuring correctness are:

1. The shortest obstacle-avoiding path consists of straight-line segments whose endpoints are either the source, the destination, or polygon vertices.

2. Two points are connected in the visibility graph if and only if the direct segment does not pass through any polygon's interior.

3. Dijkstra's algorithm finds the shortest path in the visibility graph, which corresponds to the shortest obstacle-avoiding path in the plane.

4. Limitation: The proper-intersection test handles the common case but may need refinement for degenerate configurations (e.g., a segment passing exactly through a polygon vertex). For the given problem with non-intersecting convex polygons and general position, this implementation is correct.

Complexity Analysis

• Time complexity: $O(V^2 \cdot N + V^2 \log V)$ per query, where $V$ is the total number of nodes (polygon vertices + 2 query points) and $N$ is the number of polygons. Building the visibility graph dominates: $O(V^2)$ pairs, each checked against $O(N)$ polygons' edges.

• Space complexity: $O(V^2)$ for the visibility graph.