When solving this problem, precision errors in floating-point comparisons led to multiple failed submissions despite correct algorithmic logic. The challenge lies in grouping monsters by their directional vectors and efficiently computing the number of targets hit by a laser fired in a specific direction.

Monsters are represented as coordinate pairs (x, y). To normalize directions, each vector is reduced by its greatest common divisor (GCD), ensuring identical directions map to the same normalized vector. For example, (4,6) and (2,3) become equivalent after division by GCD(4,6)=2.

Directions are sorted counter-clockwise using a custom comparator. The comparator first prioritizes vectors in the upper half-plane (y > 0) or the positive x-axis (y == 0 and x > 0). Within the same half-plane, vectors are ordered by the sign of their cross product: for two vectors (x₁,y₁) and (x₂,y₂), the condition x₁·y₂ > x₂·y₁ ensures counter-clockwise ordering.

After sorting, each direction is assigned an index, and a prefix sum array is built to quickly compute the number of monsters in any range of directions. For each query (a, b), the laser path spans the arc from monster a to monster b in counter-clockwise order. If both monsters lie on the same direction, all monsters in that group are hit. Otherwise, the total is the sum of monsters in the arc between their indices, wrapping around if necessary.

Crucially, integer arithmetic avoids floating-point inaccuracies entirely. The cross product comparison replaces atan2 or dot product-based sorting, eliminating precision-related WA issues.

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

using ll = long long;
const int MAX_N = 200005;

int n, q;
int monsterDir[MAX_N];      // Direction index of each monster
int dirCount[MAX_N];        // Number of monsters per direction
int prefixSum[MAX_N];       // Prefix sum of monster counts
map<pair<int, int>, vector<int>> dirMap;
vector<pair<int, int>> uniqueDirs;

// Comparator for counter-clockwise ordering
bool compareDirs(const pair<int, int>& a, const pair<int, int>& b) {
    int x1 = a.first, y1 = a.second;
    int x2 = b.first, y2 = b.second;

    bool inUpper1 = (y1 > 0) || (y1 == 0 && x1 > 0);
    bool inUpper2 = (y2 > 0) || (y2 == 0 && x2 > 0);

    if (inUpper1 != inUpper2) return inUpper1 > inUpper2;
    return (ll)x1 * y2 > (ll)x2 * y1; // Cross product: counter-clockwise
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        int g = gcd(abs(x), abs(y));
        if (g) { x /= g; y /= g; }
        if (dirMap[{x, y}].empty()) uniqueDirs.push_back({x, y});
        dirMap[{x, y}].push_back(i);
    }

    sort(uniqueDirs.begin(), uniqueDirs.end(), compareDirs);

    for (int i = 0; i < uniqueDirs.size(); ++i) {
        auto& monsters = dirMap[uniqueDirs[i]];
        dirCount[i + 1] = monsters.size();
        for (int m : monsters) monsterDir[m] = i + 1;
    }

    for (int i = 1; i <= uniqueDirs.size(); ++i) {
        prefixSum[i] = prefixSum[i - 1] + dirCount[i];
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        int idxA = monsterDir[a], idxB = monsterDir[b];

        if (idxA == idxB) {
            cout << dirCount[idxA] << '\n';
        } else {
            if (idxA < idxB) {
                cout << prefixSum[idxB] - prefixSum[idxA - 1] << '\n';
            } else {
                // Wrap around: from idxA to end, then from start to idxB
                cout << (prefixSum[uniqueDirs.size()] - prefixSum[idxA - 1]) + prefixSum[idxB] << '\n';
            }
        }
    }
}

F - Diagonal Separation 2

This problem requires partitioning an n×n grid along a diagonal such that the total number of '#' and '.' cells on the wrong side of the diagonal is minimized. The diagonal can be thought of as a stepwise boundary between rows, where in row i, the first j cells are on one side and the rest on the other.

A dynamic programming approach is used: let dp[i][j] represent the minimum cost to process the first i rows, with the diagonal cutting after column j in row i. The cost for row i with cut at j is the sum of '#' to the left of j and '.' to the right of j.

Naively computing dp[i][j] by checking all k ≤ j from dp[i-1][k] would result in O(n³) complexity. Instead, we optimize by maintaining a running minimum array minL[j], which stores the minimum dp[i-1][k] for all k ≥ j. This allows each dp[i][j] to be computed in O(1).

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

const int MAX_N = 2005;
const int INF = 0x3f3f3f3f;

int n;
string grid[MAX_N];
int prefixHash[MAX_N][MAX_N];   // '#' count from left to j
int suffixDot[MAX_N][MAX_N];    // '.' count from j+1 to end
int dp[MAX_N][MAX_N];           // dp[i][j]: min cost up to row i, cut after col j
int minL[MAX_N];                // minL[j] = min(dp[i-1][k]) for k >= j

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }

    // Precompute prefix '#' and suffix '.'
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            prefixHash[i][j] = prefixHash[i][j-1] + (grid[i][j] == '#');
        }
        for (int j = n; j >= 1; --j) {
            suffixDot[i][j] = suffixDot[i][j+1] + (grid[i][j] == '.');
        }
    }

    // Initialize first row
    for (int j = 0; j <= n; ++j) {
        dp[1][j] = prefixHash[1][j] + suffixDot[1][j+1];
    }

    // DP with optimization
    for (int i = 2; i <= n; ++i) {
        // Compute minL[j]: minimum dp[i-1][k] for k >= j
        minL[n+1] = INF;
        for (int j = n; j >= 0; --j) {
            minL[j] = min(minL[j+1], dp[i-1][j]);
        }

        // Update current row
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = minL[j] + prefixHash[i][j] + suffixDot[i][j+1];
        }
    }

    int ans = INF;
    for (int j = 0; j <= n; ++j) {
        ans = min(ans, dp[n][j]);
    }
    cout << ans << '\n';
}