[BOJ 13551] 원과 쿼리

https://www.acmicpc.net/problem/13551

13551번: 원과 쿼리

clang으로 냈더니 살짝 커팅한 나이브가 돌더라...ㅋㅋㅋ

https://blog.naver.com/jinhan814/222680932977 [jinhan814님 풀이]

 

코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0,&st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(T x) {
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<int> IO;

struct Pair {
    ll x, y;
    Pair() = default;
    Pair(ll _x, ll _y): x(_x), y(_y) {}
};

bool operator <(const Pair& a, const Pair &b) {
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

int n, m;
Pair a[101010];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);

    IO.set();
    n = IO.get();
    for(int i=1; i<=n; i++) {
        a[i].x = IO.get();
        a[i].y = IO.get();
    }
    sort(a + 1, a + 1 + n);
    m = IO.get();
    while(m--) {
        ll x = IO.get(), y = IO.get(), r = IO.get();
        int i = lower_bound(a + 1, a + 1 + n, Pair(x - r, 0)) - a;
        int j = upper_bound(a + 1, a + 1 + n, Pair(x + r, 1e18)) - a;
        int cnt = 0;
        for(; i<j; i++) if((a[i].x - x) * (a[i].x - x) + (a[i].y - y) * (a[i].y - y) <= r * r) {
            cnt++;
        }
        IO.put(cnt);
    }
}