백준13551 원과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/13551

사용 알고리즘

  • 버킷

풀이

2차원 평면을 여러 개의 정사각형으로 분할해서 생각해봅시다.

쿼리로 원이 주어질 때마다 모든 정사각형 조각을 보면서 아래 3가지 경우를 처리해주면 됩니다.

  • 정사각형이 원에 완전히 포함되는 경우: 해당 정사각형 영역 안에 존재하는 점의 개수를 모두 더한다.
  • 정사각형과 원이 겹치지 않는 경우: 해당 정사각형 영역 안에 존재하는 점은 무시해도 된다.
  • 일부가 겹치는 경우: 해당 정사각형 영역 안에 있는 점들을 하나씩 보면서 원 안에 들어가는지 판별해주면 된다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const int sz = 1500;
const int IN = -1;
const int NONE = 0;
const int INTERSECT = 1;

bool mid(ll a, ll b, ll c){ return a <= b && b <= c; }
inline ll dst(p p1, p p2){ ll dx = p1.x - p2.x, dy = p1.y - p2.y; return dx*dx + dy*dy; }
struct Bucket{
    ll x, xx, y, yy; vector<p> v;
    Bucket(){}
    Bucket(p x_range, p y_range){
        v.clear();
        x = x_range.x; xx = x_range.y;
        y = y_range.x; yy = y_range.y;
    }
    int chk(p pt, ll r) const {
        bool sum = false, mul = true, t; ll R = r*r;
        t = dst(pt, p(x, y)) <= R; sum |= t; mul &= t;
        t = dst(pt, p(xx, y)) <= R; sum |= t; mul &= t;
        t = dst(pt, p(x, yy)) <= R; sum |= t; mul &= t;
        t = dst(pt, p(xx, yy)) <= R; sum |= t; mul &= t;
        if(mul) return IN;
        if(sum) return INTERSECT;
        if(mid(x, pt.x, xx) && mid(y, pt.y, yy)) return INTERSECT;
        if(mid(x, pt.x, xx) && min(pt.y-y, yy-pt.y) <= r) return INTERSECT;
        if(mid(y, pt.y, yy) && min(pt.x-x, xx-pt.x) <= r) return INTERSECT;
        return NONE;
    }
};

int n, q; p a[101010];
vector<int> comp_x, comp_y;
vector<p> x_range, y_range;
vector<Bucket> buc;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i].x >> a[i].y;
        comp_x.push_back(a[i].x);
        comp_y.push_back(a[i].y);
    }
    compress(comp_x); compress(comp_y);

    for(int i=0; i<comp_x.size(); i++){
        int j = i+sz; if(j >= comp_x.size()) j = comp_x.size()-1;
        x_range.emplace_back(comp_x[i], comp_x[j]); i = j;
    }
    for(int i=0; i<comp_y.size(); i++){
        int j = i+sz; if(j >= comp_y.size()) j = comp_y.size()-1;
        y_range.emplace_back(comp_y[i], comp_y[j]); i = j;
    }

    for(int i=0; i<x_range.size(); i++) for(int j=0; j<y_range.size(); j++){
        buc.emplace_back(x_range[i], y_range[j]);
    }
    for(int i=1; i<=n; i++){
        int x_idx = upper_bound(all(x_range), p(a[i].x, 1e9)) - x_range.begin() - 1;
        int y_idx = upper_bound(all(y_range), p(a[i].y, 1e9)) - y_range.begin() - 1;
        buc[x_idx*(y_range.size())+y_idx].v.push_back(a[i]);
    }

    cin >> q;
    while(q--){
        p pt; ll r, res = 0; cin >> pt.x >> pt.y >> r;
        for(const auto &i : buc){
            int buc_res = i.chk(pt, r);
            if(buc_res == NONE) continue;
            if(buc_res == IN) res += i.v.size();
            else for(auto j : i.v) if(dst(pt, j) <= r*r) res++;
        }
        cout << res << "\n";
    }
}