USACO 2024 US Open Contest Bronze Division - Walking Along a Fence

Problem link: here

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

So we know that every query involves two points that are on the polygon and the polygon is a well formed polygon.

An important thing to know is that the coordinates of the points are up to 1000, so there are at most \(10^6\) relevant points.

Because of this reason, we can precompute the place where each point is, relative to the first point. Now we need to compute the slope of each line to see if it's vertical or horizontal. Then, we can keep track of how many points we visited so far and then after we are done, we can solve each query by knowing where the two points sit relative to each other and the minimum distance will be min (the distance between them, total distance - that distance between them).

In order to find that distance, we will rely on knowing that the points are in some sort of a circle and there are two cases we have to deal with.

Source codes

The source codes in C++ and Python can be seen below.

#include <iostream>
using namespace std;

int q, n, X[200002], Y[200002], pos[1002][1002];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> q >> n;

    for(int i = 1; i <= n; i++)
        cin >> X[i] >> Y[i];

    X[n+1] = X[1];
    Y[n+1] = Y[1];

    int cnt = 1;
    for(int i = 1; i <= n; i++)
    {
        int slope_x = 0, slope_y = 0;
        if(X[i] < X[i+1])
            slope_x = 1;
        if(X[i] > X[i+1])
            slope_x = -1;
        if(Y[i] < Y[i+1])
            slope_y = 1;
        if(Y[i] > Y[i+1])
            slope_y = -1;
        for(int xj = X[i] + slope_x, yj = Y[i] + slope_y; ; xj += slope_x, yj += slope_y)
        {
            cnt++;
            pos[xj][yj] = cnt;
            if(xj == X[i+1] && yj == Y[i+1])
                break;
        }
    }
    pos[X[1]][Y[1]] = 1;
    cnt--;

    for(int i = 1; i <= q; i++)
    {
        int xa, ya, xb, yb;
        cin >> xa >> ya >> xb >> yb;

        int dist = pos[xb][yb] - pos[xa][ya];
        if(dist < 0)
            dist += cnt;

        cout << min(dist, cnt - dist) << '\n';
    }
    return 0;
}

import sys
data = sys.stdin.read().split()
idx = 0

q = int(data[idx])
idx += 1
n = int(data[idx])
idx += 1

X = [0] * (n + 2)
Y = [0] * (n + 2)

for i in range(1, n + 1):
    X[i] = int(data[idx])
    idx += 1
    Y[i] = int(data[idx])
    idx += 1

X[n + 1] = X[1]
Y[n + 1] = Y[1]
pos = [[0] * 1003 for _ in range(1003)]

cnt = 1

for i in range(1, n + 1):
    slope_x = 0
    slope_y = 0
    if X[i] < X[i + 1]:
        slope_x = 1
    elif X[i] > X[i + 1]:
        slope_x = -1

    if Y[i] < Y[i + 1]:
        slope_y = 1
    elif Y[i] > Y[i + 1]:
        slope_y = -1

    xj = X[i] + slope_x
    yj = Y[i] + slope_y
    while True:
        cnt += 1
        pos[xj][yj] = cnt
        if xj == X[i + 1] and yj == Y[i + 1]:
            break
        xj += slope_x
        yj += slope_y

pos[X[1]][Y[1]] = 1
cnt -= 1

output_lines = []
for _ in range(q):
    xa = int(data[idx])
    idx += 1
    ya = int(data[idx])
    idx += 1
    xb = int(data[idx])
    idx += 1
    yb = int(data[idx])
    idx += 1

    dist = pos[xb][yb] - pos[xa][ya]
    if dist < 0:
        dist += cnt

    answer = min(dist, cnt - dist)
    output_lines.append(str(answer))

sys.stdout.write("\n".join(output_lines))