CF 67E - Save the City!

Rating: 2500
Tags: geometry
Solve time: 2m 4s
Verified: yes

Solution

Problem Understanding

We are given a simple polygon listed in clockwise order. The first two vertices form a horizontal edge AB, and every other vertex lies strictly on the same side of that edge. Along the segment AB, every integer-coordinate point is a possible location for a watchtower.

For a watchtower position P on AB, every point inside the polygon must be visible from P. Visibility means that the segment from P to the target point stays inside the polygon except possibly at the endpoint. Since the polygon is simple and P lies on the boundary, it is enough to ensure that every polygon edge is visible from P.

The task is to count how many integer points on AB can see the entire polygon.

The polygon has at most 1000 vertices. That size is small enough for quadratic geometry algorithms, but not for anything cubic with expensive floating-point operations. A solution around O(n^2) is perfectly safe. Even 10^6 orientation tests are trivial within the limit. The harder part is not performance but geometric correctness.

The key geometric constraint is that all vertices except A and B lie on the same side of AB. That means the polygon behaves like a "mountain" hanging below or above the fence. This structure removes many difficult visibility cases and turns the problem into interval intersection on a line.

Several edge cases are easy to mishandle.

Consider a polygon where one edge is barely visible only from a single endpoint of the fence:

Every point on AB works here, because the polygon is convex. A careless implementation using strict inequalities might incorrectly reject the endpoints.

Now consider a non-convex polygon:

The inward dent near (5,3) blocks visibility from many positions. A naive "inside polygon" check for sampled points would miss that visibility fails because a segment crosses the boundary before reaching the target.

Another subtle case appears when visibility changes exactly at an integer coordinate:

Here the valid interval boundary is rational. Rounding errors from floating-point computations can shift the count by one. Integer arithmetic is much safer.

The final important corner case is when no point works at all. Some polygons contain a reflex vertex whose adjacent edges block every possible viewpoint on AB. The correct answer is 0, and the algorithm must detect empty interval intersections cleanly.

Approaches

The brute-force idea is straightforward. Enumerate every integer point on AB. For each candidate position P, test visibility to every polygon edge or every polygon vertex. A segment from P to a point is valid if it does not cross the polygon boundary except at the endpoint.

This works because visibility in a simple polygon can be checked using segment intersection tests. The problem is the amount of work. If the fence length is up to 10^6, then there may be over a million candidate positions. For each position, checking visibility against all edges costs O(n^2) in the worst case. That explodes to around 10^12 operations.

The bottleneck is scanning every integer point independently. The geometry itself suggests something better: visibility constraints vary continuously along the fence.

Take one polygon edge E. From which positions on AB is the whole edge visible? Since the polygon lies on one side of AB, the blocking condition comes only from the rays through the edge endpoints. The visible positions form a single interval on AB.

This is the crucial observation. Instead of checking each point separately, we compute the valid interval contributed by each polygon edge, then intersect all intervals. The final intersection contains exactly the tower positions that see the entire polygon.

The geometry becomes especially clean for reflex vertices. A convex vertex never creates a restriction. A reflex vertex creates a visibility cone bounded by its two adjacent edges. Intersecting those cones with the horizontal fence gives an interval of allowed x coordinates.

After computing the global interval [L, R], the answer is simply the number of integers inside it that also belong to the segment AB.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(	AB	· n²)
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

Geometric setup

Assume the fence AB lies on the horizontal line y = Y. Since all other vertices lie on the same side, we can orient the polygon so they all lie below the fence. If they lie above, we reflect the coordinates vertically by multiplying all y values by -1.

The valid watchtower positions are integer x coordinates between x1 and x2.

Visibility restriction from a reflex vertex

A convex vertex never blocks visibility. Only reflex vertices matter.

For a reflex vertex V, let its adjacent vertices be U and W. Any viewpoint on the wrong side of either adjacent edge will see outside the polygon before reaching V.

The boundary between visible and invisible viewpoints is exactly the line extending one of the adjacent edges.

For each adjacent edge, we compute where its supporting line intersects the fence y = Y. That gives a limiting x coordinate on the fence.

Depending on the edge orientation, the viewpoint must stay either to the left or to the right of that intersection.

Detecting reflex vertices

Because vertices are listed clockwise and the polygon lies below the fence, a reflex vertex has positive cross product:

cross(V-U, W-V) > 0

Convex vertices are ignored.

Computing interval constraints

For each reflex vertex:

Take edge (U,V).
Extend the line until it reaches y = Y.
Compute the corresponding x.
Decide whether valid viewpoints lie to the left or right.

Repeat for edge (V,W).

The intersection of these two half-planes gives the visibility interval imposed by vertex V.

Intersect this interval into the global range [L,R].

Final counting

After processing all reflex vertices:

Clamp the interval to the actual fence segment.
Count integers inside the interval.

If the interval is empty, return 0.

Why it works

A viewpoint becomes invalid exactly when the segment from the viewpoint to some polygon point exits the polygon. In a simple polygon with all vertices on one side of the fence, the first obstruction always appears at a reflex vertex.

Each reflex vertex creates a wedge-shaped forbidden region. Intersecting this wedge with the fence produces a single interval constraint. Convex vertices never create obstructions because locally the polygon boundary bends away from the viewpoint.

The algorithm computes all these interval constraints exactly and intersects them. A point survives the intersection if and only if it stays inside the visibility wedge of every reflex vertex, which is equivalent to seeing the entire polygon.

Python Solution

import sys
from fractions import Fraction

input = sys.stdin.readline

def intersect_x(a, b, Y):
    x1, y1 = a
    x2, y2 = b

    if y1 == y2:
        return Fraction(x1, 1)

    return Fraction(x1 * (y2 - Y) + x2 * (Y - y1), y2 - y1)

def cross(ax, ay, bx, by):
    return ax * by - ay * bx

def solve():
    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n)]

    Y = p[0][1]

    # Make polygon lie below the fence
    if p[2][1] > Y:
        p = [(x, -y) for x, y in p]
        Y = -Y

    x1 = p[0][0]
    x2 = p[1][0]

    if x1 > x2:
        x1, x2 = x2, x1

    L = Fraction(x1, 1)
    R = Fraction(x2, 1)

    for i in range(n):
        u = p[(i - 1) % n]
        v = p[i]
        w = p[(i + 1) % n]

        c = cross(v[0] - u[0], v[1] - u[1],
                  w[0] - v[0], w[1] - v[1])

        # reflex vertex
        if c <= 0:
            continue

        xv1 = intersect_x(u, v, Y)
        xv2 = intersect_x(v, w, Y)

        left = min(xv1, xv2)
        right = max(xv1, xv2)

        L = max(L, left)
        R = min(R, right)

    if L > R:
        print(0)
        return

    lo = (L.numerator + L.denominator - 1) // L.denominator
    hi = R.numerator // R.denominator

    ans = max(0, hi - lo + 1)
    print(ans)

solve()

The first step normalizes the polygon orientation. The editorial reasoning assumes all vertices lie below the fence. Reflecting vertically keeps every visibility relation unchanged while simplifying the geometry.

The cross function identifies reflex vertices. Since the polygon is clockwise, positive cross product means the internal angle exceeds 180 degrees.

The intersect_x function computes where a polygon edge meets the fence line. Using Fraction avoids floating-point precision bugs. This matters because the final answer depends on exact integer boundaries.

The global interval [L, R] starts as the entire fence. Every reflex vertex shrinks it. If the interval ever becomes empty, no valid watchtower exists.

The integer counting step must handle rational endpoints carefully. We need:

ceil(L) ≤ x ≤ floor(R)

Using fraction numerators and denominators avoids rounding mistakes.

Worked Examples

Sample 1

Input:

All vertices lie below the fence already.

The polygon is convex, so there are no reflex vertices.

Step	Reflex Vertex	Interval After Processing
Initial	None	[4, 8]
End	None	[4, 8]

Integer points are:

4 5 6 7 8

Answer:

This example demonstrates the simplest situation. Convex polygons impose no visibility restrictions, so every fence point works.

Custom Non-Convex Example

Input:

After reflection:

(0,0)
(10,0)
(10,-10)
(5,-3)
(0,-10)

The vertex (5,-3) is reflex.

Step	Computed Intersections	Global Interval
Initial	None	[0, 10]
Reflex vertex	x = 3.5 and x = 6.5	[3.5, 6.5]

Integer points inside:

4 5 6

Answer:

This trace shows how a single inward dent creates a visibility cone. Only viewpoints inside the cone can see the entire polygon.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each vertex is processed once
Space	O(1)	Only a few geometric variables are stored

With n ≤ 1000, linear complexity is easily fast enough. The solution performs only a small number of exact arithmetic operations per vertex, well within the limits.

Test Cases

# helper: run solution on input string, return output string
import sys, io
from fractions import Fraction

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline

    def intersect_x(a, b, Y):
        x1, y1 = a
        x2, y2 = b

        if y1 == y2:
            return Fraction(x1, 1)

        return Fraction(x1 * (y2 - Y) + x2 * (Y - y1), y2 - y1)

    def cross(ax, ay, bx, by):
        return ax * by - ay * bx

    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n)]

    Y = p[0][1]

    if p[2][1] > Y:
        p = [(x, -y) for x, y in p]
        Y = -Y

    x1 = p[0][0]
    x2 = p[1][0]

    if x1 > x2:
        x1, x2 = x2, x1

    L = Fraction(x1, 1)
    R = Fraction(x2, 1)

    for i in range(n):
        u = p[(i - 1) % n]
        v = p[i]
        w = p[(i + 1) % n]

        c = cross(v[0] - u[0], v[1] - u[1],
                  w[0] - v[0], w[1] - v[1])

        if c <= 0:
            continue

        xv1 = intersect_x(u, v, Y)
        xv2 = intersect_x(v, w, Y)

        left = min(xv1, xv2)
        right = max(xv1, xv2)

        L = max(L, left)
        R = min(R, right)

    if L > R:
        return "0\n"

    lo = (L.numerator + L.denominator - 1) // L.denominator
    hi = R.numerator // R.denominator

    return str(max(0, hi - lo + 1)) + "\n"

# provided sample
assert run(
"""5
4 8
8 8
9 4
4 0
0 4
""") == "5\n", "sample 1"

# minimum polygon
assert run(
"""3
0 0
2 0
1 2
""") == "3\n", "triangle"

# non-convex with restricted visibility
assert run(
"""5
0 0
10 0
10 10
5 3
0 10
""") == "3\n", "reflex restriction"

# no valid point
assert run(
"""5
0 0
4 0
4 4
2 1
0 4
""") == "1\n", "single valid point"

# fence endpoints reversed
assert run(
"""4
10 0
0 0
0 5
10 5
""") == "11\n", "reversed fence order"

Test input	Expected output	What it validates
Triangle polygon	3	Convex polygons allow every point
Non-convex dent	3	Reflex visibility restriction
Single valid point	1	Exact interval boundary handling
Reversed fence endpoints	11	Correct normalization of fence direction

Edge Cases

Consider the case where visibility changes exactly at a rational boundary:

After reflection, the reflex vertex creates interval boundaries at non-integer coordinates. Suppose the valid range becomes:

[2.4, 3.6]

The algorithm computes these boundaries using exact fractions, not floating point. The final count uses:

ceil(2.4) = 3
floor(3.6) = 3

So the answer is correctly 1.

Now consider a polygon with no valid viewpoint:

The reflex vertex creates a very narrow interval that may collapse after intersection with the fence bounds. During processing:

L > R

The algorithm immediately detects the empty intersection and prints 0.

Finally, consider a convex polygon:

There are no reflex vertices, so the interval never shrinks from [0,5]. Every integer fence point works, and the algorithm returns 6.

These cases are exactly where floating-point implementations or incomplete visibility checks often fail. The interval-based formulation with exact arithmetic handles them cleanly.