백준 31786 최고의 친구

https://boj.ma/31786/t 

31786번: 최고의 친구

 

2가지 쿼리가 주어집니다.

1번 쿼리 : $(x, 0), (-x, 0)$ 에 위치할때 통신 가능한 기지국의 개수 출력

2번 쿼리 : $(x, y)$ 에 기지국이 있었으면 삭제, 없었으면 추가

 

$(x, 0)$ 와 $(-x, 0)$ 이 통신하기 위해서는 어떤 기지국 $(a, b)$ 에 대해 세 점이 이루는 삼각형이 예각 삼각형이어야 합니다.

 

1번 쿼리를 보고 예각 삼각형이 되어야 하므로 당연히 점 $(a, b)$ 의 a가 $ -x < a < x $ 여야 한다는 건 알았습니다.

처음엔 저 사이에만 있으면 무조건 예각삼각형이라고 착각했습니다.

 

중3때 배우는 기하학을 갖고와봅시다

반원에 대한 원주각은 항상 직각입니다.

$(x, 0)$ 와 $(-x, 0)$ 을 지름으로 하는, 반지름의 길이가 x이고 중심이 $(0, 0)$인 원을 생각하면

원안에 있는 모든 점들에 대해서 만들어지는 삼각형은 절대 예각삼각형이 될 수 없습니다.

 

따라서 임의의 기지국 좌표 $(a, b)$에 대해 $ -x < a < x $ 를 만족하면서  $ a^2 + b^2 > x^2$ 인 점들만 답이 될 수 있습니다.

그럼  $ -x < a < x $ 의 개수에서 $ a^2 + b^2 <= x^2$ 인 점의 개수를 빼주면 1번 쿼리를 처리할 수 있습니다.

 

쿼리의 개수가 $3*10^5$개 주어지는 좌표의 범위가 $[-10^9, 10^9]$ 이므로 당연히 완전탐색으로 쿼리를 처리할 수 없습니다.

 

1번쿼리는 특정 범위인 값의 개수, 2번쿼리는 특정 좌표를 추가하거나 삭제하는 쿼리이므로

세그먼트 트리를 생각할 수 있습니다.

그런데, 좌표의 범위가 크기때문에 좌표압축을 해줘야할 것 같은데 온라인으로 좌표가 주어지기때문에 힘들어 보입니다.

 

그래서 쿼리를 미리 다 받아서 나올 수 있는 모든 $x$좌표와 $x^2+y^2$의 값을 미리 계산하여 좌표압축 후에

세그먼트 트리를 적용하면 됩니다.

 

여기까지 생각하고 세그먼트 트리를 통해 구현을 하다가 pbds를 통해서도 충분히 위의 쿼리를 처리할 수 있다고 판단하여 pbds로 구현했습니다.

 

그리고, $x^2 + y^2$의 값들을 관리할때 좌표가 다르더라도 $x^2 + y^2$의 결과는 같을 수 있습니다.

따라서 기지국의 좌표를 따로 관리하는 자료구조(set, map..)도 필요합니다.

 

구현(c++)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 100000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 i128;
using namespace std;

//pbds -- order_of_key(x) := x미만의 원소의 개수(x가 들어가야할 인덱스 0-based) , find_by_order(k) := (k + 1)번째 원소가 있는 iter
using namespace __gnu_pbds;
// multi-set
using ordered_set_equal = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using ordered_set_equal_pll = tree<pll, null_type, less_equal<pll>, rb_tree_tag, tree_order_statistics_node_update>;
// set
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ordered_set_equal x_, xy_;
    ordered_set_equal_pll xy_cd;
    // multi-set 원소삭제
    auto pbds_erase = [&](ordered_set_equal &a, ll val)->void{
        auto it = a.find_by_order(a.order_of_key(val));
        if(*it == val) a.erase(it);
    };

    auto pbds_erase_pll = [&](ordered_set_equal_pll &a, pll val) -> void{
        auto it = a.find_by_order(a.order_of_key(val));
        if (*it == val) a.erase(it);
    };

    int q;
    cin >> q;
    while(q--){
        int oper;
        cin >> oper;
        if (oper&1){
            ll x;
            cin >> x;
            // (-x, x)구간의 갯수
            int x_cnt = x_.order_of_key(x) - x_.order_of_key(-x + 1);
            // a^2 + b^2 <= x^2인 (a, b)의 갯수
            int xy_cnt = xy_.order_of_key(x * x + 1);
            cout << x_cnt - xy_cnt<< endl;
        }else{
            ll x, y;
            cin >> x >> y;
            // x^2 + y^2
            ll cur = x * x + y * y;
            auto it = xy_cd.find_by_order(xy_cd.order_of_key({x, y}));
            // 이미 존재하는 기지국
            if (it->first == x && it->second == y) {
                pbds_erase(xy_, cur);
                pbds_erase(x_, x);
                pbds_erase_pll(xy_cd, make_pair(x, y));
            }else{
                xy_.insert(cur);
                x_.insert(x);
                xy_cd.insert(make_pair(x, y));
            }
        }
    }

    return 0;
}

 

 

 

기지국의 좌표를 관리하는건 굳이 pbds를 통해 관리하지 않아도 됩니다.

 

 

 

 

사진 출처 : http://trsketch.dothome.co.kr/a13012