DartsInter-Uni Programming Contest Tasks Leaderboard Contest

Description：

Darts
https://interunia.unswcpmsoc.com/task/Darts/

Thinking：

This contest is harder than I imaged, this is the second task, and I spent a lot of time but when I checked the Leaderboard and no one has solved it yet, I feel a little bit better.
At first, I thought of simply judging whether this point is in the middle of this circle, using Euclidean distance calculation. But later I found that when there are n circles and m darts, the amount of data is surprisingly large. After the brute force cracking timed out, I had to consider a new method.

We can use the gridded Spatial Indexing, the specific steps are as follows:

1. Spatial division: Divide the entire plane into grids of equal size (Grid), and map the target and dart to the corresponding grid.

Purpose:

• Reduce the number of targets that need to be calculated.
• For each dart, you only need to check the targets in its grid and adjacent grids.

2. Map Targets to Grids:

• Calculate the bounding box of each target.
  • Lower-left corner: ( (x_i - r_i, y_i - r_i) )
  • Upper-right corner: ( (x_i + r_i, y_i + r_i) )
• Record all grid cells covered by this rectangle and add the target index to these grid cells.

3. Map Darts to Grids:

For each dart, calculate the grid coordinates where it is located.

4. Check if the Dart Hits a Target:

• For each dart, check all targets in its grid and the adjacent 8 grids.
• Calculate the distance from the dart to the center of each target and determine whether it is less than or equal to the square of the target’s radius, i.e., ( (dx - x_i)^2 + (dy - y_i)^2 \leq r_i^2 ).

Grid Division Parameters

Grid size (GRID_SIZE):

• Choose an appropriate grid size, such as 500.
• The choice of grid size requires a trade-off between space and time efficiency.

auto get_grid_cell = [&](long long x_n, long long y_n) {
    int gx = int((x_n - min_x) / s);
    int gy = int((y_n - min_y) / s);
    return make_pair(gx, gy);
};

Coordinate mapping function:

Maps actual coordinates to grid coordinates.

• s is the actual length of each grid cell.
• $min_x$ and $min_y$ are the minimum values among all target and dart coordinates, used to shift the coordinates.

Mapping Targets to Grids

• Iterate over all targets and calculate their covered grid ranges.
• In these grids, record the indices of the targets.

for (int idx = 0; idx < n; ++idx) {
    int x, y, r;
    tie(x, y, r) = circles[idx];
    long long x_min = x - r;
    long long x_max = x + r;
    long long y_min = y - r;
    long long y_max = y + r;
    auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
    auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
    for (int gx = gx_min; gx <= gx_max; ++gx) {
        for (int gy = gy_min; gy <= gy_max; ++gy) {
            long long key = get_grid_key(gx, gy);
            grid[key].push_back(idx); // 存储靶子索引
        }
    }
}

Mapping Darts to Grids

• For each dart, calculate the grid cell it belongs to.
• No need to store darts in grids; we process them directly.

Checking if Darts Hit Targets

• For each dart, get its grid coordinates ( (gx, gy) ).
• Check the dart’s grid cell and its 8 adjacent grid cells.
• For each target in these grids, calculate the distance to the dart.
• If the distance squared is less than or equal to the target’s radius squared, increment the counter.

for (const auto& p : points) {
    int dx = p.first;
    int dy = p.second;
    auto [gx, gy] = get_grid_cell(dx, dy);
    bool found = false;
    
    // Check the grid and the 8 adjacent grids
    for (int ix = gx - 1; ix <= gx + 1; ++ix) {
        for (int iy = gy - 1; iy <= gy + 1; ++iy) {
            long long key = get_grid_key(ix, iy);
            if (grid.count(key)) {
                const auto& circle_indices = grid[key];
                for (int idx : circle_indices) {
                    int x, y, r;
                    tie(x, y, r) = circles[idx];
                    // caculate the distance
                    long long dx_sq = (long long)(dx - x) * (dx - x);
                    long long dy_sq = (long long)(dy - y) * (dy - y);
                    long long r_sq = (long long)r * r;
                    if (dx_sq + dy_sq <= r_sq) {
                        ans++;
                        found = true;
                        break; // The dart has found the target, check the next dart
                    }
                }
            }
            if (found) break;
        }
        if (found) break;
    }
}

code:

import math

n, m = map(int, input().split())

circles = []

min_x = min_y = float('inf')
max_x = max_y = float('-inf')

for _ in range(n):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
    min_x = min(min_x, x - r)
    max_x = max(max_x, x + r)
    min_y = min(min_y, y - r)
    max_y = max(max_y, y + r)

points = []

for _ in range(m):
    dx, dy = map(int, input().split())
    points.append((dx, dy))
    min_x = min(min_x, dx)
    max_x = max(max_x, dx)
    min_y = min(min_y, dy)
    max_y = max(max_y, dy)

GRID_SIZE = 500
delta_x = max_x - min_x
delta_y = max_y - min_y
s = max(delta_x, delta_y) / GRID_SIZE
if s == 0:
    s = 1

# Function that maps coordinates to grid indices
def get_grid_cell(x_n, y_n):
    gx = int((x_n - min_x) / s)
    gy = int((y_n - min_y) / s)
    return gx, gy

grid = {}

# Mapping the targets onto the grid
for idx, (x, y, r) in enumerate(circles):
    x_min = x - r
    x_max = x + r
    y_min = y - r
    y_max = y + r
    gx_min, gy_min = get_grid_cell(x_min, y_min)
    gx_max, gy_max = get_grid_cell(x_max, y_max)
    for gx in range(gx_min, gx_max + 1):
        for gy in range(gy_min, gy_max + 1):
            if (gx, gy) not in grid:
                grid[(gx, gy)] = []
            grid[(gx, gy)].append(idx)  # store the target index

ans = 0

# For each dart, check the target in the grid where it is located
for dx, dy in points:
    gx, gy = get_grid_cell(dx, dy)
    found = False
    if (gx, gy) in grid:
        for idx in grid[(gx, gy)]:
            x, y, r = circles[idx]
            # Determine if the dart is in the target
            if (dx - x) ** 2 + (dy - y) ** 2 <= r ** 2:
                ans += 1
                found = True
                break  # 找到后跳出循环
    # The grids do not overlap and the surrounding grids are not detected?

print(ans)

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // Fast input/output
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> circles;
    long long min_x = LLONG_MAX, min_y = LLONG_MAX;
    long long max_x = LLONG_MIN, max_y = LLONG_MIN;

    // Read circles and update bounding box
    for (int i = 0; i < n; ++i) {
        int x, y, r;
        cin >> x >> y >> r;
        circles.emplace_back(x, y, r);
        min_x = min(min_x, (long long)x - r);
        max_x = max(max_x, (long long)x + r);
        min_y = min(min_y, (long long)y - r);
        max_y = max(max_y, (long long)y + r);
    }

    vector<pair<int, int>> points;

    // Read darts and update bounding box
    for (int i = 0; i < m; ++i) {
        int dx, dy;
        cin >> dx >> dy;
        points.emplace_back(dx, dy);
        min_x = min(min_x, (long long)dx);
        max_x = max(max_x, (long long)dx);
        min_y = min(min_y, (long long)dy);
        max_y = max(max_y, (long long)dy);
    }

    const int GRID_SIZE = 500;
    long long delta_x = max_x - min_x;
    long long delta_y = max_y - min_y;
    double s = max(delta_x, delta_y) / (double)GRID_SIZE;
    if (s == 0) {
        s = 1;
    }

    // Function to get grid cell indices
    auto get_grid_cell = [&](long long x_n, long long y_n) {
        int gx = int((x_n - min_x) / s);
        int gy = int((y_n - min_y) / s);
        return make_pair(gx, gy);
    };

    // Function to combine gx and gy into a single key
    auto get_grid_key = [](int gx, int gy) -> long long {
        return ((long long)gx << 32) | (unsigned int)gy;
    };

    // Map from grid cell key to list of circle indices
    unordered_map<long long, vector<int>> grid;

    // Map circles to grid cells
    for (int idx = 0; idx < n; ++idx) {
        int x, y, r;
        tie(x, y, r) = circles[idx];
        long long x_min = x - r;
        long long x_max = x + r;
        long long y_min = y - r;
        long long y_max = y + r;
        auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
        auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
        for (int gx = gx_min; gx <= gx_max; ++gx) {
            for (int gy = gy_min; gy <= gy_max; ++gy) {
                long long key = get_grid_key(gx, gy);
                grid[key].push_back(idx); // Store circle index
            }
        }
    }

    int ans = 0;

    // For each dart, check circles in its grid cell and adjacent cells
    for (const auto& p : points) {
        int dx = p.first;
        int dy = p.second;
        auto [gx, gy] = get_grid_cell(dx, dy);
        bool found = false;

        // Check the dart's grid cell and its 8 neighbors
        for (int ix = gx - 1; ix <= gx + 1; ++ix) {
            for (int iy = gy - 1; iy <= gy + 1; ++iy) {
                long long key = get_grid_key(ix, iy);
                if (grid.count(key)) {
                    const auto& circle_indices = grid[key];
                    for (int idx : circle_indices) {
                        int x, y, r;
                        tie(x, y, r) = circles[idx];
                        // Check if the dart is inside the circle
                        long long dx_sq = (long long)(dx - x) * (dx - x);
                        long long dy_sq = (long long)(dy - y) * (dy - y);
                        long long r_sq = (long long)r * r;
                        if (dx_sq + dy_sq <= r_sq) {
                            ans++;
                            found = true;
                            break; // Move to next dart
                        }
                    }
                }
                if (found) break;
            }
            if (found) break;
        }
    }

    cout << ans << '\n';
    return 0;
}