EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All ICPC entries
Competitive Programming

ICPC 2021 - D. Guardians of the Gallery

We are given a simple polygon, the guard position, and the center of a sculpture. The guard may move only inside the polygon, and we want the minimum distance needed to reach a position from which at least half of an...

Source sync Apr 19, 2026
Track ICPC
Year 2021
Files TeX, C++, statement assets
Folder competitive_programming/icpc/2021/D-guardians-of-the-gallery
ICPC2021TeXC++statement textstatement pdf
Source of truth

Source-first archive entry

This page is built from the copied files in competitive_programming/icpc/2021/D-guardians-of-the-gallery. Edit competitive_programming/icpc/2021/D-guardians-of-the-gallery/solution.tex to update the written solution and competitive_programming/icpc/2021/D-guardians-of-the-gallery/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++ Meta JSON
Problem statement

Problem Statement

Copied statement text kept beside the solution archive for direct reference.

Raw text Statement PDF 
Problem D
                                Guardians of the Gallery
                                        Time limit: 5 seconds
Your local art gallery is about to host an exciting new exhibition of sculptures by world-renowned artists,
and the gallery expects to attract thousands of visitors. Unfortunately, the exhibition might also attract
the wrong kind of visitors, namely burglars who intend to steal the works of art. In the past, the gallery
directors did not worry much about this problem, since their permanent collection is, to be honest, not
really worth stealing.
The gallery consists of rooms, and each sculpture in the new exhibition will be placed in a different
room. Each room has a security guard and an alarm to monitor the artwork. When an alarm sounds, the
guard will run (without leaving the room) from their post to a position where they can see the sculpture
directly. This is to check whether the sculpture has in fact been stolen, or whether this is yet another
false alarm.
To figure out where to best station the security guard, the gallery directors would like to know how long
it takes for the guard to see a given sculpture. They hope that you can help!
Every room is on a single floor, and the layout of the walls can be approximated by a simple polygon.
The locations of the guard and the sculpture are distinct points strictly inside the polygon. The sculpture
is circular, with a negligibly small (but positive) radius. To verify that the sculpture is still present, the
guard needs to be able to see at least half of it.
Figure D.1 illustrates two examples. In each case, the guard starts at the blue square on the left, and the
sculpture is located at the red circle on the right. The dotted blue line shows the optimal path for the
guard to move. Once the guard reaches the location marked by the green diamond, half of the sculpture
can be seen.

                   (a) Sample Input 1                                    (b) Sample Input 2

                                 Figure D.1: Illustration of sample inputs.

Input

The first line of input contains an integer n (3 ≤ n ≤ 100), the number of vertices that describe the
polygon. This is followed by n lines each containing two integers x and y (0 ≤ x, y ≤ 1 000), giving
the coordinates of the polygon vertices in counterclockwise order. The next line contains two integers
xg and yg , which specify the location of the guard. Finally, the last line contains two integers xs and ys ,
which specify the location of the center of the sculpture. The polygon is simple, that is, its vertices are
distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at
their common vertex. In addition, no two consecutive edges are collinear.

Output

Output the minimum distance that the guard has to move to be able to see at least half the sculpture.
Your answer must have an absolute or relative error of at most 10−6 .

 Sample Input 1                                    Sample Output 1
 8                                                 58.137767414994535
 0 0
 20 0
 20 30
 60 30
 60 0
 80 0
 80 50
 0 50
 10 10
 70 10

 Sample Input 2                                    Sample Output 2
 11                                                2.0
 0 0
 4 0
 4 1
 5 1
 5 0
 7 0
 7 2
 3 2
 3 1
 2 2
 0 2
 1 1
 6 1
Editorial

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

  • Fix a ray starting at the sculpture center and going outward. As we move along that ray, the only moments when the visibility status can change are when the ray hits the polygon boundary.

  • A proper crossing of the ray by the polygon boundary blocks both halves of the sculpture at once. A tangent touch blocks only one side. Along one ray, the guard may continue moving until both sides have been blocked at least once.

  • Therefore, on every relevant ray, the valid positions form one prefix segment starting at the sculpture center and ending at the first point where both sides are blocked.

  • The only rays that matter are the rays passing through polygon vertices. Between two consecutive such rays, the combinatorial description of the blocking boundary does not change.

  • Once these boundary rays are known, the rest is a standard shortest-path-in-polygon problem: a shortest path bends only at polygon vertices, and the final straight segment ends on one of the boundary spokes.

  1. For every polygon vertex $v$, consider the ray from the sculpture center $s$ through $v$.

  2. For one fixed ray, scan all polygon edges:

    • if an edge crosses the ray properly, it blocks both sides;

    • if a boundary vertex lies on the ray, inspect the two polygon chains incident to that vertex: if they approach the ray from opposite sides, this is also a two-sided block; otherwise it is a one-sided block.

    • Let $t_+$ and $t_-$ be the first distances on the ray where the positive and negative side become blocked. The usable part of the ray ends at \[ \max(t_+, t_-). \]

    • Rays with the same direction are merged, keeping only the farthest reachable endpoint. This gives a set of boundary spokes, each represented by one segment from $s$ to its cutoff point.

    • Build the usual visibility graph on the guard and all polygon vertices. Two nodes are connected if the straight segment between them lies inside the polygon closure.

    • Run Dijkstra from the guard to all graph nodes.

    • For each graph node $q$ and each boundary spoke $T$:

      • compute the subset of $T$ directly visible from $q$;

      • add the distance from $q$ to the nearest visible point of $T$.

      • The visible subset of one spoke is found by splitting the spoke at all parameters where the line from $q$ to the spoke passes through a polygon vertex. Between two consecutive split points, the visibility status is constant, so a midpoint test is enough.

      • Also check whether the guard itself, or any polygon vertex reached by Dijkstra, already lies in the valid region. enumerate

        We prove that the algorithm returns the correct answer.

        Lemma 1.

        Along a fixed ray starting at the sculpture center, the set of valid guard positions is exactly one prefix segment of that ray.

        Proof.

        Moving outward along the ray can only lose visibility, never regain it, because every blocking event lies between the sculpture and all farther points on the same ray.

        A proper crossing of the boundary blocks both sides of the tiny circle immediately. A tangential contact blocks only one side. To see at least half of the sculpture, at least one side must remain unblocked. Hence the valid points are precisely those before the first position where both sides have been blocked. So the valid set on that ray is one prefix segment. □

        Lemma 2.

        The endpoint of the valid prefix on a ray is completely determined by polygon edges and vertices lying on that ray, and only rays through polygon vertices can change the combinatorial answer.

        Proof.

        Between two consecutive rays through polygon vertices, every polygon edge stays on the same side of the ray, so the ordering of one-sided and two-sided blocking events does not change. Therefore the cutoff value varies continuously without changing combinatorial type, and all changes happen exactly at rays through vertices. The cutoff on such a ray is determined by the first blocking event on each side, which comes from the ray hitting polygon edges or polygon vertices. □

        Lemma 3.

        There exists an optimal path that consists of a shortest path from the guard to some visibility-graph node, followed by one straight segment to a boundary spoke.

        Proof.

        The valid region is contained in the polygon and is bounded by the spokes computed above. Any shortest path inside a simple polygon bends only at polygon vertices; the last bend before entering the target region is therefore either the guard itself or a polygon vertex. From that final bend, the remainder of the path is a straight segment to the first point where the path enters the target region, and that entry point lies on the boundary of the target region, hence on one of the boundary spokes. □

        Lemma 4.

        For a fixed graph node $q$ and a fixed spoke $T$, splitting $T$ at parameters where the line $qx$ passes through a polygon vertex is sufficient to determine all directly visible subsegments of $T$.

        Proof.

        As the endpoint $x$ moves continuously along $T$, the segment $qx$ can change its intersection pattern with the polygon boundary only when it passes through a polygon vertex. Between two consecutive such events, no combinatorial change is possible, so the visibility status is constant on the whole open subsegment. Therefore midpoint testing on each interval is sufficient. □

        Theorem.

        The algorithm outputs the correct answer for every valid input.

        Proof.

        By Lemmas 1 and 2, the algorithm computes exactly the boundary spokes of the valid region. By Lemma 3, some optimal path is represented by a visibility-graph path to a node $q$ and one final straight segment from $q$ to a spoke. By Lemma 4, the algorithm checks exactly all such final straight segments. Dijkstra provides the correct shortest distance from the guard to every possible last bend. Taking the minimum over all graph nodes and all spokes therefore yields the true optimum. □

        Let $n$ be the number of polygon vertices.

        • Computing all spoke cutoffs costs $O(n^2)$.

        • Building the visibility graph costs $O(n^3)$ because there are $O(n)$ nodes and each visibility test against the polygon costs $O(n)$.

        • For every graph node and every spoke, we split by all polygon vertices and run $O(n)$ segment tests, so this phase is $O(n^4)$.

        • With $n \le 100$, this is easily fast enough. Memory usage is $O(n^2)$.

        • Boundary points are allowed. Geometrically, standing exactly on a limiting spoke corresponds to seeing exactly half of the infinitesimal circle, which is valid.

        • The code tests segment containment in the polygon by collecting all boundary-intersection parameters, then checking the midpoint of every open interval between them.

        • Several vertices can lie on the same ray from the sculpture; those rays are merged by normalized direction.

Source code

Code

Exact copied C++ implementation from solution.cpp.

C++ competitive_programming/icpc/2021/D-guardians-of-the-gallery/solution.cpp

Exact copied implementation source.

Raw file 
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

namespace {

const long double EPS = 1e-12L;
const long double INF = 1e100L;

struct Point {
    long double x;
    long double y;
};

Point operator+(const Point& a, const Point& b) {
    return {a.x + b.x, a.y + b.y};
}

Point operator-(const Point& a, const Point& b) {
    return {a.x - b.x, a.y - b.y};
}

Point operator*(const Point& a, long double t) {
    return {a.x * t, a.y * t};
}

long double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

long double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

long double norm(const Point& a) {
    return sqrtl(dot(a, a));
}

int sgn(long double x) {
    if (x > EPS) {
        return 1;
    }
    if (x < -EPS) {
        return -1;
    }
    return 0;
}

bool point_on_segment(const Point& p, const Point& a, const Point& b) {
    return fabsl(cross(a - p, b - p)) <= 1e-10L && dot(a - p, b - p) <= 1e-10L;
}

// Returns 1 for inside, 0 for boundary, -1 for outside.
int point_location(const vector<Point>& poly, const Point& p) {
    int winding = 0;
    int n = static_cast<int>(poly.size());
    for (int i = 0; i < n; ++i) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];

        if (point_on_segment(p, a, b)) {
            return 0;
        }

        if (a.y <= p.y + EPS) {
            if (b.y > p.y + EPS && cross(b - a, p - a) > EPS) {
                ++winding;
            }
        } else {
            if (b.y <= p.y + EPS && cross(b - a, p - a) < -EPS) {
                --winding;
            }
        }
    }
    return winding == 0 ? -1 : 1;
}

bool segment_inside_polygon(const vector<Point>& poly, const Point& p, const Point& q) {
    vector<long double> parameters;
    parameters.push_back(0.0L);
    parameters.push_back(1.0L);

    Point d = q - p;
    long double dd = dot(d, d);
    int n = static_cast<int>(poly.size());

    for (int i = 0; i < n; ++i) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];
        Point edge = b - a;
        Point ap = a - p;
        long double den = cross(d, edge);

        if (fabsl(den) <= EPS) {
            if (fabsl(cross(d, ap)) <= EPS && dd > EPS) {
                long double ta = dot(a - p, d) / dd;
                long double tb = dot(b - p, d) / dd;
                if (ta > -EPS && ta < 1.0L + EPS) {
                    parameters.push_back(max(0.0L, min(1.0L, ta)));
                }
                if (tb > -EPS && tb < 1.0L + EPS) {
                    parameters.push_back(max(0.0L, min(1.0L, tb)));
                }
            }
            continue;
        }

        long double t = cross(ap, edge) / den;
        long double u = cross(ap, d) / den;
        if (t > -EPS && t < 1.0L + EPS && u > -EPS && u < 1.0L + EPS) {
            parameters.push_back(max(0.0L, min(1.0L, t)));
        }
    }

    sort(parameters.begin(), parameters.end());
    vector<long double> unique_parameters;
    for (size_t i = 0; i < parameters.size(); ++i) {
        if (unique_parameters.empty() || fabsl(parameters[i] - unique_parameters.back()) > 1e-11L) {
            unique_parameters.push_back(parameters[i]);
        }
    }

    for (size_t i = 0; i + 1 < unique_parameters.size(); ++i) {
        long double l = unique_parameters[i];
        long double r = unique_parameters[i + 1];
        if (r - l < 1e-11L) {
            continue;
        }
        Point mid = p + d * ((l + r) * 0.5L);
        if (point_location(poly, mid) < 0) {
            return false;
        }
    }

    for (int i = 0; i < n; ++i) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];
        Point edge = b - a;
        Point ap = a - p;
        long double den = cross(d, edge);
        if (fabsl(den) <= EPS) {
            continue;
        }
        long double t = cross(ap, edge) / den;
        long double u = cross(ap, d) / den;
        if (t > EPS && t < 1.0L - EPS && u > EPS && u < 1.0L - EPS) {
            return false;
        }
    }

    return true;
}

long double ray_cutoff(const vector<Point>& poly, const Point& sculpture, const Point& direction) {
    int n = static_cast<int>(poly.size());
    long double dd = dot(direction, direction);

    auto parameter_on_ray = [&](const Point& p) {
        return dot(direction, p - sculpture) / dd;
    };

    long double both_sides = INF;
    long double positive_side = INF;
    long double negative_side = INF;

    for (int i = 0; i < n; ++i) {
        Point a = poly[i];
        Point b = poly[(i + 1) % n];
        int sa = sgn(cross(direction, a - sculpture));
        int sb = sgn(cross(direction, b - sculpture));
        if (sa == 0 || sb == 0) {
            continue;
        }
        if (sa != sb) {
            Point edge = b - a;
            long double den = cross(direction, edge);
            long double t = cross(a - sculpture, edge) / den;
            if (t > EPS) {
                both_sides = min(both_sides, t);
            }
        }
    }

    vector<int> on_ray(n, 0);
    vector<long double> ray_parameter(n, 0.0L);
    for (int i = 0; i < n; ++i) {
        long double t = parameter_on_ray(poly[i]);
        if (sgn(cross(direction, poly[i] - sculpture)) == 0 && t > EPS) {
            on_ray[i] = 1;
            ray_parameter[i] = t;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!on_ray[i]) {
            continue;
        }
        int left = (i - 1 + n) % n;
        while (on_ray[left]) {
            left = (left - 1 + n) % n;
        }
        int right = (i + 1) % n;
        while (on_ray[right]) {
            right = (right + 1) % n;
        }

        int sl = sgn(cross(direction, poly[left] - sculpture));
        int sr = sgn(cross(direction, poly[right] - sculpture));
        long double t = ray_parameter[i];

        if (sl != sr) {
            both_sides = min(both_sides, t);
        } else if (sl > 0) {
            positive_side = min(positive_side, t);
        } else {
            negative_side = min(negative_side, t);
        }
    }

    long double left_block = min(both_sides, positive_side);
    long double right_block = min(both_sides, negative_side);
    return max(left_block, right_block);
}

struct Segment {
    Point a;
    Point b;
};

long double distance_point_to_segment(const Point& p, const Segment& segment) {
    Point d = segment.b - segment.a;
    long double dd = dot(d, d);
    if (dd <= EPS) {
        return norm(p - segment.a);
    }
    long double t = dot(p - segment.a, d) / dd;
    t = max(0.0L, min(1.0L, t));
    Point projection = segment.a + d * t;
    return norm(p - projection);
}

long double visible_distance_to_segment(const vector<Point>& poly, const Point& from, const Segment& segment) {
    vector<long double> events;
    events.push_back(0.0L);
    events.push_back(1.0L);

    Point dir = segment.b - segment.a;
    for (size_t i = 0; i < poly.size(); ++i) {
        Point to_vertex = poly[i] - from;
        long double den = cross(dir, to_vertex);
        long double num = cross(segment.a - from, to_vertex);

        if (fabsl(den) <= EPS) {
            if (fabsl(num) <= EPS) {
                long double dd = dot(dir, dir);
                if (dd > EPS) {
                    long double t = dot(poly[i] - segment.a, dir) / dd;
                    if (t > -EPS && t < 1.0L + EPS) {
                        events.push_back(max(0.0L, min(1.0L, t)));
                    }
                }
            }
            continue;
        }

        long double t = -num / den;
        if (t > -EPS && t < 1.0L + EPS) {
            events.push_back(max(0.0L, min(1.0L, t)));
        }
    }

    sort(events.begin(), events.end());
    vector<long double> unique_events;
    for (size_t i = 0; i < events.size(); ++i) {
        if (unique_events.empty() || fabsl(events[i] - unique_events.back()) > 1e-11L) {
            unique_events.push_back(events[i]);
        }
    }

    long double best = INF;

    for (size_t i = 0; i < unique_events.size(); ++i) {
        Point candidate = segment.a + dir * unique_events[i];
        if (segment_inside_polygon(poly, from, candidate)) {
            best = min(best, norm(candidate - from));
        }
    }

    for (size_t i = 0; i + 1 < unique_events.size(); ++i) {
        long double l = unique_events[i];
        long double r = unique_events[i + 1];
        if (r - l < 1e-11L) {
            continue;
        }

        Point mid = segment.a + dir * ((l + r) * 0.5L);
        if (!segment_inside_polygon(poly, from, mid)) {
            continue;
        }

        Segment visible_part = {segment.a + dir * l, segment.a + dir * r};
        best = min(best, distance_point_to_segment(from, visible_part));
    }

    return best;
}

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void solve() {
    int n;
    cin >> n;

    vector<Point> polygon(n);
    vector<pair<int, int> > polygon_int(n);
    for (int i = 0; i < n; ++i) {
        cin >> polygon_int[i].first >> polygon_int[i].second;
        polygon[i] = {static_cast<long double>(polygon_int[i].first),
                      static_cast<long double>(polygon_int[i].second)};
    }

    Point guard;
    Point sculpture;
    cin >> guard.x >> guard.y;
    cin >> sculpture.x >> sculpture.y;

    map<pair<int, int>, pair<long double, Point> > best_segment;
    for (int i = 0; i < n; ++i) {
        long long dx = polygon_int[i].first - static_cast<long long>(llround(sculpture.x));
        long long dy = polygon_int[i].second - static_cast<long long>(llround(sculpture.y));
        long long g = gcd_ll(llabs(dx), llabs(dy));
        dx /= g;
        dy /= g;

        Point direction = polygon[i] - sculpture;
        long double cutoff = ray_cutoff(polygon, sculpture, direction);
        Point endpoint = sculpture + direction * cutoff;
        long double projection = dot(endpoint - sculpture,
                                     {static_cast<long double>(dx), static_cast<long double>(dy)});

        pair<int, int> key = {static_cast<int>(dx), static_cast<int>(dy)};
        if (best_segment.find(key) == best_segment.end() ||
            projection > best_segment[key].first + 1e-10L) {
            best_segment[key] = {projection, endpoint};
        }
    }

    vector<Segment> target_segments;
    for (map<pair<int, int>, pair<long double, Point> >::const_iterator it = best_segment.begin();
         it != best_segment.end(); ++it) {
        target_segments.push_back({sculpture, it->second.second});
    }

    vector<Point> nodes;
    nodes.push_back(guard);
    for (int i = 0; i < n; ++i) {
        nodes.push_back(polygon[i]);
    }

    int node_count = static_cast<int>(nodes.size());
    vector<vector<pair<int, long double> > > graph(node_count);
    for (int i = 0; i < node_count; ++i) {
        for (int j = i + 1; j < node_count; ++j) {
            if (segment_inside_polygon(polygon, nodes[i], nodes[j])) {
                long double w = norm(nodes[i] - nodes[j]);
                graph[i].push_back({j, w});
                graph[j].push_back({i, w});
            }
        }
    }

    vector<long double> dist(node_count, INF);
    vector<int> used(node_count, 0);
    dist[0] = 0.0L;
    for (int iter = 0; iter < node_count; ++iter) {
        int best = -1;
        for (int i = 0; i < node_count; ++i) {
            if (!used[i] && (best == -1 || dist[i] < dist[best])) {
                best = i;
            }
        }
        if (best == -1 || dist[best] >= INF / 2) {
            break;
        }
        used[best] = 1;
        for (size_t i = 0; i < graph[best].size(); ++i) {
            int to = graph[best][i].first;
            long double w = graph[best][i].second;
            if (dist[to] > dist[best] + w) {
                dist[to] = dist[best] + w;
            }
        }
    }

    long double answer = INF;

    if (ray_cutoff(polygon, sculpture, guard - sculpture) >= 1.0L - 1e-11L) {
        answer = 0.0L;
    }

    for (int i = 0; i < node_count; ++i) {
        if (dist[i] >= INF / 2) {
            continue;
        }

        if (ray_cutoff(polygon, sculpture, nodes[i] - sculpture) >= 1.0L - 1e-11L) {
            answer = min(answer, dist[i]);
        }

        for (size_t j = 0; j < target_segments.size(); ++j) {
            long double last_leg = visible_distance_to_segment(polygon, nodes[i], target_segments[j]);
            if (last_leg < INF / 2) {
                answer = min(answer, dist[i] + last_leg);
            }
        }
    }

    cout << setprecision(15) << static_cast<double>(answer) << '\n';
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Source files

Source Files

Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.

TeX write-up competitive_programming/icpc/2021/D-guardians-of-the-gallery/solution.tex

Exact copied write-up source.

Raw file 
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2021\\D. Guardians of the Gallery}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

We are given a simple polygon, the guard position, and the center of a sculpture. The guard may move
only inside the polygon, and we want the minimum distance needed to reach a position from which at
least half of an infinitesimally small circular sculpture is visible.

So the real task is:
\begin{itemize}[leftmargin=*]
    \item describe the region of points from which the sculpture is ``visible enough'',
    \item then find the shortest path from the guard to that region.
\end{itemize}

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item Fix a ray starting at the sculpture center and going outward. As we move along that ray, the
    only moments when the visibility status can change are when the ray hits the polygon boundary.

    \item A \emph{proper crossing} of the ray by the polygon boundary blocks both halves of the sculpture
    at once. A \emph{tangent touch} blocks only one side. Along one ray, the guard may continue moving
    until both sides have been blocked at least once.

    \item Therefore, on every relevant ray, the valid positions form one prefix segment starting at the
    sculpture center and ending at the first point where both sides are blocked.

    \item The only rays that matter are the rays passing through polygon vertices. Between two consecutive
    such rays, the combinatorial description of the blocking boundary does not change.

    \item Once these boundary rays are known, the rest is a standard shortest-path-in-polygon problem:
    a shortest path bends only at polygon vertices, and the final straight segment ends on one of the
    boundary spokes.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item For every polygon vertex $v$, consider the ray from the sculpture center $s$ through $v$.

    \item For one fixed ray, scan all polygon edges:
    \begin{itemize}[leftmargin=*]
        \item if an edge crosses the ray properly, it blocks both sides;
        \item if a boundary vertex lies on the ray, inspect the two polygon chains incident to that vertex:
        if they approach the ray from opposite sides, this is also a two-sided block; otherwise it is a
        one-sided block.
    \end{itemize}
    Let $t_+$ and $t_-$ be the first distances on the ray where the positive and negative side become
    blocked. The usable part of the ray ends at
    \[
        \max(t_+, t_-).
    \]

    \item Rays with the same direction are merged, keeping only the farthest reachable endpoint. This gives
    a set of boundary spokes, each represented by one segment from $s$ to its cutoff point.

    \item Build the usual visibility graph on the guard and all polygon vertices. Two nodes are connected if
    the straight segment between them lies inside the polygon closure.

    \item Run Dijkstra from the guard to all graph nodes.

    \item For each graph node $q$ and each boundary spoke $T$:
    \begin{itemize}[leftmargin=*]
        \item compute the subset of $T$ directly visible from $q$;
        \item add the distance from $q$ to the nearest visible point of $T$.
    \end{itemize}
    The visible subset of one spoke is found by splitting the spoke at all parameters where the line from
    $q$ to the spoke passes through a polygon vertex. Between two consecutive split points, the visibility
    status is constant, so a midpoint test is enough.

    \item Also check whether the guard itself, or any polygon vertex reached by Dijkstra, already lies in
    the valid region.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
Along a fixed ray starting at the sculpture center, the set of valid guard positions is exactly one prefix
segment of that ray.

\paragraph{Proof.}
Moving outward along the ray can only lose visibility, never regain it, because every blocking event lies
between the sculpture and all farther points on the same ray.

A proper crossing of the boundary blocks both sides of the tiny circle immediately. A tangential contact
blocks only one side. To see at least half of the sculpture, at least one side must remain unblocked.
Hence the valid points are precisely those before the first position where both sides have been blocked.
So the valid set on that ray is one prefix segment. \qed

\paragraph{Lemma 2.}
The endpoint of the valid prefix on a ray is completely determined by polygon edges and vertices lying on
that ray, and only rays through polygon vertices can change the combinatorial answer.

\paragraph{Proof.}
Between two consecutive rays through polygon vertices, every polygon edge stays on the same side of the
ray, so the ordering of one-sided and two-sided blocking events does not change. Therefore the cutoff
value varies continuously without changing combinatorial type, and all changes happen exactly at rays
through vertices. The cutoff on such a ray is determined by the first blocking event on each side, which
comes from the ray hitting polygon edges or polygon vertices. \qed

\paragraph{Lemma 3.}
There exists an optimal path that consists of a shortest path from the guard to some visibility-graph node,
followed by one straight segment to a boundary spoke.

\paragraph{Proof.}
The valid region is contained in the polygon and is bounded by the spokes computed above. Any shortest
path inside a simple polygon bends only at polygon vertices; the last bend before entering the target
region is therefore either the guard itself or a polygon vertex. From that final bend, the remainder of the
path is a straight segment to the first point where the path enters the target region, and that entry point
lies on the boundary of the target region, hence on one of the boundary spokes. \qed

\paragraph{Lemma 4.}
For a fixed graph node $q$ and a fixed spoke $T$, splitting $T$ at parameters where the line $qx$ passes
through a polygon vertex is sufficient to determine all directly visible subsegments of $T$.

\paragraph{Proof.}
As the endpoint $x$ moves continuously along $T$, the segment $qx$ can change its intersection pattern
with the polygon boundary only when it passes through a polygon vertex. Between two consecutive such
events, no combinatorial change is possible, so the visibility status is constant on the whole open
subsegment. Therefore midpoint testing on each interval is sufficient. \qed

\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.

\paragraph{Proof.}
By Lemmas 1 and 2, the algorithm computes exactly the boundary spokes of the valid region.
By Lemma 3, some optimal path is represented by a visibility-graph path to a node $q$ and one final
straight segment from $q$ to a spoke. By Lemma 4, the algorithm checks exactly all such final straight
segments. Dijkstra provides the correct shortest distance from the guard to every possible last bend.
Taking the minimum over all graph nodes and all spokes therefore yields the true optimum. \qed

\section*{Complexity Analysis}

Let $n$ be the number of polygon vertices.

\begin{itemize}[leftmargin=*]
    \item Computing all spoke cutoffs costs $O(n^2)$.
    \item Building the visibility graph costs $O(n^3)$ because there are $O(n)$ nodes and each visibility
    test against the polygon costs $O(n)$.
    \item For every graph node and every spoke, we split by all polygon vertices and run $O(n)$ segment
    tests, so this phase is $O(n^4)$.
\end{itemize}

With $n \le 100$, this is easily fast enough. Memory usage is $O(n^2)$.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item Boundary points are allowed. Geometrically, standing exactly on a limiting spoke corresponds to
    seeing exactly half of the infinitesimal circle, which is valid.
    \item The code tests segment containment in the polygon by collecting all boundary-intersection
    parameters, then checking the midpoint of every open interval between them.
    \item Several vertices can lie on the same ray from the sculpture; those rays are merged by normalized
    direction.
\end{itemize}

\end{document}