結果

問題 No.202 1円玉投げ
ユーザー izuru_matsuura
提出日時 2016-09-22 22:30:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 522 ms / 5,000 ms
コード長 4,209 bytes
コンパイル時間 2,331 ms
コンパイル使用メモリ 183,416 KB
実行使用メモリ 82,708 KB
最終ジャッジ日時 2024-12-22 10:29:53
合計ジャッジ時間 10,990 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define whole(xs) xs.begin(),xs.end()

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        auto i = vs.begin();
        os << "[" << *i;
        for (++i; i != vs.end(); ++i) os << " " << *i;
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    struct Point {
        ll x, y;
        int id;
        Point() {}
        Point(ll x, ll y) : x(x), y(y) {}
        static bool compX(const Point& a, const Point& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
        static bool compY(const Point& a, const Point& b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
    };
    istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }
    ostream& operator<<(ostream& os, const Point& p) { return os << "Point(" << p.x << "," << p.y << ")"; }
    struct Node {
        Node* parent;
        shared_ptr<Node> left, right;
        ll left_x, right_x;
        vector<Point> ys;
    };
    //ostream& operator<<(ostream& os, const Node& node) {
    //    return os << "( [" << node.left_x << "," << node.right_x << "] -> " << node.ys;
    //}
    shared_ptr<Node> construct(vector<Point>::iterator lb, vector<Point>::iterator ub) {
        auto n = make_shared<Node>();
        n->left_x = lb->x;
        n->right_x = (ub - 1)->x;
        if (ub - lb == 1) {
            n->ys.clear(); n->ys.push_back(*lb);
            return n;
        }
        auto mid = lb + (ub - lb) / 2;
        auto l = construct(lb, mid),
             r = construct(mid, ub);
        l->parent = n.get();
        r->parent = n.get();
        n->left = l;
        n->right = r;
        size_t li = 0, ri = 0;
        while (true) {
            if (li >= l->ys.size() && ri >= r->ys.size()) break;
            if (li >= l->ys.size()) n->ys.push_back(r->ys[ri++]);
            else if (ri >= r->ys.size()) n->ys.push_back(l->ys[li++]);
            else {
                n->ys.push_back( l->ys[li].y < r->ys[ri].y ? l->ys[li++] : r->ys[ri++] );
            }
        }
        return n;
    }

    /* (sx <= x <= gx && sy <= y <= gy)縺ｪ繧狗せ(x, y)繧池esult縺ｫ蜈･繧後ｋ. 髢牙玄髢薙↑縺ｮ豕ｨ諢・*/
    void query(shared_ptr<Node> root, ll sx, ll sy, ll gx, ll gy, vector<Point>& result) {
        if (gx < root->left_x || root->right_x < sx) {
            // do nothing;
        } else if (sx <= root->left_x && root->right_x <= gx) {
            auto& ys = root->ys;
            auto lb = upper_bound(whole(ys), Point(0, sy - 1), Point::compY);
            auto ub = lower_bound(whole(ys), Point(0, gy + 1), Point::compY);
            result.insert(result.end(), lb, ub);
        } else {
            query(root->left, sx, sy, gx, gy, result);
            query(root->right, sx, sy, gx, gy, result);
        }
    }

    int N;
    vector<Point> P;
    void input() {
        cin >> N;
        P.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> P[i]; P[i].id = i;
        }
    }

    ll dist2(const Point& a, const Point& b) {
        ll dx = a.x - b.x;
        ll dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    void solve() {
        vector<Point> Q = P;
        sort(Q.begin(), Q.end(), Point::compX);
        auto root = construct(Q.begin(), Q.end());
        int ans = 0;
        vector<bool> used(N, false);
        for (int i = 0; i < N; i++) {
            ll x = P[i].x;
            ll y = P[i].y;
            vector<Point> res;
            query(root, x - 20, y - 20, x + 20, y + 20, res);
            bool flag = false;
            for (auto p : res) {
                if (dist2(P[i], p) >= 400) continue;
                if (not used[p.id]) continue;
                flag = true;
                break;
            }
            if (not flag) {
                used[i] = true;
                ans++;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}
0