IOI 2002 - Bus Terminals

// IOI 2002 - Bus Terminals
// Partition N points into 2 groups, place a terminal for each group.
// Minimize the maximum Manhattan distance from any point to its terminal.
// Approach: Rotate coordinates (u=x+y, v=x-y) to convert Manhattan to L_inf.
// Binary search on answer R, check if points can be covered by two 2R-side squares.
// Split by u-sorted or v-sorted order and check prefix/suffix bounding boxes.
// Complexity: O(N log N + N log C) time, O(N) space.

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    if (N == 0) {
        cout << 0 << "\n";
        return 0;
    }

    vector<long long> u(N), v(N);
    for (int i = 0; i < N; i++) {
        long long x, y;
        cin >> x >> y;
        u[i] = x + y;
        v[i] = x - y;
    }

    if (N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    // Sort indices by u-coordinate
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return u[a] < u[b]; });

    // Precompute suffix min/max of v (sorted by u)
    vector<long long> suffMinV(N + 1), suffMaxV(N + 1);
    suffMinV[N] = LLONG_MAX;
    suffMaxV[N] = LLONG_MIN;
    for (int i = N - 1; i >= 0; i--) {
        suffMinV[i] = min(suffMinV[i + 1], v[idx[i]]);
        suffMaxV[i] = max(suffMaxV[i + 1], v[idx[i]]);
    }

    // Check if points can be split by u-sorted order into two groups,
    // each fitting in a 2R x 2R square
    auto checkByU = [&](long long twoR) -> bool {
        long long prefMinV = LLONG_MAX, prefMaxV = LLONG_MIN;
        for (int i = 0; i < N; i++) {
            prefMinV = min(prefMinV, v[idx[i]]);
            prefMaxV = max(prefMaxV, v[idx[i]]);
            long long prefUR = u[idx[i]] - u[idx[0]];
            long long prefVR = prefMaxV - prefMinV;
            if (prefUR <= twoR && prefVR <= twoR) {
                if (i == N - 1) return true;
                long long sufUR = u[idx[N - 1]] - u[idx[i + 1]];
                long long sufVR = suffMaxV[i + 1] - suffMinV[i + 1];
                if (sufUR <= twoR && sufVR <= twoR) return true;
            }
        }
        return false;
    };

    // Sort indices by v-coordinate
    vector<int> idxV(N);
    iota(idxV.begin(), idxV.end(), 0);
    sort(idxV.begin(), idxV.end(), [&](int a, int b) { return v[a] < v[b]; });

    // Precompute suffix min/max of u (sorted by v)
    vector<long long> suffMinU(N + 1), suffMaxU(N + 1);
    suffMinU[N] = LLONG_MAX;
    suffMaxU[N] = LLONG_MIN;
    for (int i = N - 1; i >= 0; i--) {
        suffMinU[i] = min(suffMinU[i + 1], u[idxV[i]]);
        suffMaxU[i] = max(suffMaxU[i + 1], u[idxV[i]]);
    }

    // Check if points can be split by v-sorted order
    auto checkByV = [&](long long twoR) -> bool {
        long long prefMinU = LLONG_MAX, prefMaxU = LLONG_MIN;
        for (int i = 0; i < N; i++) {
            prefMinU = min(prefMinU, u[idxV[i]]);
            prefMaxU = max(prefMaxU, u[idxV[i]]);
            long long prefVR = v[idxV[i]] - v[idxV[0]];
            long long prefUR = prefMaxU - prefMinU;
            if (prefVR <= twoR && prefUR <= twoR) {
                if (i == N - 1) return true;
                long long sufVR = v[idxV[N - 1]] - v[idxV[i + 1]];
                long long sufUR = suffMaxU[i + 1] - suffMinU[i + 1];
                if (sufVR <= twoR && sufUR <= twoR) return true;
            }
        }
        return false;
    };

    auto feasible = [&](long long twoR) -> bool {
        return checkByU(twoR) || checkByV(twoR);
    };

    // Binary search on 2R (the side length of covering squares)
    long long lo = 0, hi = 4000000000LL;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(mid))
            hi = mid;
        else
            lo = mid + 1;
    }

    // lo is the minimum 2R in L_inf = minimum max Manhattan distance
    cout << lo << "\n";

    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage[margin=1in]{geometry}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!60!black},
  stringstyle=\color{red},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2002 -- Bus Terminals}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement Summary}
Given $N$ points ($N \le 20{,}000$) in the plane, choose two terminal
locations $T_1, T_2$ and assign each point to one of them so as to
minimize the maximum Manhattan distance from any point to its assigned
terminal:
\[
  \min_{T_1,T_2,\sigma}\; \max_{i}\; d_{\text{Man}}(p_i, T_{\sigma(i)}).
\]

\section{Solution: Rotation + Binary Search}

\subsection{Rotation to $L_\infty$}
Under the change of coordinates $u = x + y$, $v = x - y$, Manhattan
distance becomes Chebyshev ($L_\infty$) distance:
\[
  |x_1 - x_2| + |y_1 - y_2| = \max(|u_1 - u_2|, |v_1 - v_2|).
\]
A ``ball'' of radius $R$ in $L_\infty$ is an axis-aligned square of
side $2R$.

\subsection{Binary Search on the Answer}
Binary search on $R$ (half the side of each covering square). For a
given $R$, check whether the point set can be covered by two
axis-aligned squares of side $2R$.

\subsection{Feasibility Check}
A set of points fits inside a $2R \times 2R$ square if and only if its
bounding box has width $\le 2R$ and height $\le 2R$.

To check whether two such squares suffice, try splitting the points
into a \emph{prefix} and a \emph{suffix} along one sorted coordinate:
\begin{enumerate}
  \item Sort points by $u$-coordinate. For each split position $i$,
        the prefix $[0,i]$ fits in a square iff its $u$-range and
        $v$-range are both $\le 2R$. Likewise check the suffix.
  \item Repeat with points sorted by $v$-coordinate, splitting along $v$.
\end{enumerate}
If either splitting direction yields a valid partition, $R$ is feasible.

\begin{lemma}
Trying both splitting directions (by $u$ and by $v$) is sufficient.
Any optimal two-square cover admits a separating line parallel to one
of the axes in the rotated coordinate system.
\end{lemma}

\section{C++ Implementation}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    vector<long long> u(N), v(N);
    for (int i = 0; i < N; i++) {
        long long x, y;
        cin >> x >> y;
        u[i] = x + y;
        v[i] = x - y;
    }

    // --- Sort by u and precompute suffix v-extremes ---
    vector<int> idxU(N);
    iota(idxU.begin(), idxU.end(), 0);
    sort(idxU.begin(), idxU.end(),
         [&](int a, int b) { return u[a] < u[b]; });

    vector<long long> sufMinV(N + 1), sufMaxV(N + 1);
    sufMinV[N] = LLONG_MAX;  sufMaxV[N] = LLONG_MIN;
    for (int i = N - 1; i >= 0; i--) {
        sufMinV[i] = min(sufMinV[i + 1], v[idxU[i]]);
        sufMaxV[i] = max(sufMaxV[i + 1], v[idxU[i]]);
    }

    auto checkU = [&](long long twoR) -> bool {
        long long pMinV = LLONG_MAX, pMaxV = LLONG_MIN;
        for (int i = 0; i < N; i++) {
            pMinV = min(pMinV, v[idxU[i]]);
            pMaxV = max(pMaxV, v[idxU[i]]);
            if (u[idxU[i]] - u[idxU[0]] <= twoR &&
                pMaxV - pMinV <= twoR) {
                if (i == N - 1) return true;
                long long sUR = u[idxU[N - 1]] - u[idxU[i + 1]];
                long long sVR = sufMaxV[i + 1] - sufMinV[i + 1];
                if (sUR <= twoR && sVR <= twoR) return true;
            }
        }
        return false;
    };

    // --- Sort by v and precompute suffix u-extremes ---
    vector<int> idxV(N);
    iota(idxV.begin(), idxV.end(), 0);
    sort(idxV.begin(), idxV.end(),
         [&](int a, int b) { return v[a] < v[b]; });

    vector<long long> sufMinU(N + 1), sufMaxU(N + 1);
    sufMinU[N] = LLONG_MAX;  sufMaxU[N] = LLONG_MIN;
    for (int i = N - 1; i >= 0; i--) {
        sufMinU[i] = min(sufMinU[i + 1], u[idxV[i]]);
        sufMaxU[i] = max(sufMaxU[i + 1], u[idxV[i]]);
    }

    auto checkV = [&](long long twoR) -> bool {
        long long pMinU = LLONG_MAX, pMaxU = LLONG_MIN;
        for (int i = 0; i < N; i++) {
            pMinU = min(pMinU, u[idxV[i]]);
            pMaxU = max(pMaxU, u[idxV[i]]);
            if (v[idxV[i]] - v[idxV[0]] <= twoR &&
                pMaxU - pMinU <= twoR) {
                if (i == N - 1) return true;
                long long sVR = v[idxV[N - 1]] - v[idxV[i + 1]];
                long long sUR = sufMaxU[i + 1] - sufMinU[i + 1];
                if (sVR <= twoR && sUR <= twoR) return true;
            }
        }
        return false;
    };

    auto feasible = [&](long long twoR) -> bool {
        return checkU(twoR) || checkV(twoR);
    };

    // Binary search: twoR = 2R is the side length of each square.
    // The answer (max Manhattan distance) equals twoR / 2 = R,
    // but since L_inf distance R = Manhattan distance R, the answer
    // is simply R = twoR (the Chebyshev radius, which equals the
    // Manhattan radius due to the rotation).
    long long lo = 0, hi = 4000000000LL;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";

    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}
\begin{itemize}
  \item \textbf{Time:} $O(N \log N + N \log C)$ where $C$ is the
        coordinate range. Sorting is $O(N \log N)$; each feasibility
        check is $O(N)$; binary search runs $O(\log C)$ iterations.
  \item \textbf{Space:} $O(N)$.
\end{itemize}

\end{document}