BZOJ1199 [HNOI2005]汤姆的游戏

2015.03.04 16:27 Wed| 0 visits oi_2015| 2015_刷题日常| Text

Solution

将询问点按照横坐标排序,然后对于一个图形,二分查找出横坐标上可能被这个图形覆盖的点的范围,然后对于这个范围内的点直接暴力即可。

—— 《论随机数据的优越性》

Code

#include <bits/stdc++.h>
using namespace std;
#define sqr(x) ((x) * (x))
#define N 250005

int n, m, cntr, cntc, ans[N];

struct point
{
    int id; double x, y;
    point(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    inline void read(int _id) { id = _id; scanf("%lf%lf", &x, &y); }
    inline bool operator <(const point &p) const { return x < p.x; }
} p[N];

struct square
{
    double x1, y1, x2, y2;
    inline void read() { scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); }
    inline bool check(const point &p) { return p.y > y1 && p.y < y2; }
    inline double left() { return x1; }
    inline double right() { return x2; }
} r[N];

struct circle
{
    double x, y, r;
    inline void read() { scanf("%lf%lf%lf", &x, &y, &r); }
    inline bool check(const point &p)
    { return sqr(x - p.x) + sqr(y - p.y) < sqr(r); }
    inline double left() { return x - r; }
    inline double right() { return x + r; }
} c[N];

int main()
{
    cin >> n >> m;
    char opt[3];
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", opt);
        if (opt[0] == 'r') r[++cntr].read();
        else c[++cntc].read();
    }
    for (int i = 1; i <= m; ++i)
        p[i].read(i);
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= cntr; ++i)
    {
        int b = upper_bound(p + 1, p + m + 1, point(r[i].left())) - p,
            e = lower_bound(p + 1, p + m + 1, point(r[i].right())) - p - 1;
        for (int j = b; j <= e; ++j)
            if (r[i].check(p[j]))
                ++ans[p[j].id];
    }
    for (int i = 1; i <= cntc; ++i)
    {
        int b = upper_bound(p + 1, p + m + 1, point(c[i].left())) - p,
            e = lower_bound(p + 1, p + m + 1, point(c[i].right())) - p - 1;
        for (int j = b; j <= e; ++j)
            if (c[i].check(p[j]))
                ++ans[p[j].id];
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
}