学步园

题目链接：uva 1517 - Tracking RFIDs

题目大意：给定S，R，W，P，表示有R个传感器，感应半径为R，W堵墙，P个产品，给定S个传感器的位置，W堵墙的位置（两端点），以及P个产品的位置。输出每个产品可以被那些传感器确定位置。如果传感器和产品之间隔着k堵墙，则距离要加上k。

解题思路：S个数很大，但是R很小，所以枚举每个产品周围坐标加减R的距离范围内的点，判断是否存在传感器，如果存在判断距离是否满足，判断距离的时候要枚举墙的位置，判断两条线段是否相交，利用向量叉积的性质判断即可。

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct point {
    int x, y;
    point (int x = 0, int y = 0) {
        this->x = x;
        this->y = y;
    }

    point operator + (const point& u) {
        return point(x + u.x, y + u.y);
    }
    point operator - (const point& u) {
        return point(x - u.x, y - u.y);
    }
    int operator ^ (const point& u) {
        return x * u.y - y * u.x;
    }
    bool operator < (const point& u) const {
        if (x != u.x)
            return x < u.x;
        return y < u.y;
    }
};
typedef pair<point, point> line;

int S, R, W, P;
set<point> pset;
vector<line> pline;

void init () {
    pset.clear();
    pline.clear();
    scanf("%d%d%d%d", &S, &R, &W, &P);

    point u, v;
    for (int i = 0; i < S; i++) {
        scanf("%d%d", &u.x, &u.y);
        pset.insert(u);
    }

    for (int i = 0; i < W; i++) {
        scanf("%d%d%d%d", &u.x, &u.y, &v.x, &v.y);
        pline.push_back(make_pair(u, v));
    }
}

bool check (point a, point b, point c, point d) {
    if (max(a.x, b.x) < min(c.x, d.x) ||
        max(a.y, b.y) < min(c.y, d.y) ||
        min(a.x, b.x) > max(c.x, d.x) ||
        min(a.y, b.y) > max(c.y, d.y) )
        return false;

    ll i = (b - a) ^ (b - c);
    ll j = (b - a) ^ (b - d);
    ll p = (d - c) ^ (d - a);
    ll q = (d - c) ^ (d - b);
    return i * j <= 0 && p * q <= 0;
}

bool judge (point u, int x, int y) {
    if (x * x + y * y > R * R)
        return false;
    point v = u + point(x, y);

    if (!pset.count(v))
        return false;

    int cnt = 0;
    for (int i = 0; i < W; i++) {
        if (check(u, v, pline[i].first, pline[i].second))
            cnt++;
    }
    if (cnt > R)
        return false;
    return x * x + y * y <= (R - cnt) * (R - cnt);
}

void solve () {
    point u;
    vector<point> ans;

    for (int i = 0; i < P; i++) {
        ans.clear();
        scanf("%d%d", &u.x, &u.y);

        for (int x = -R; x <= R; x++) {
            for (int y = -R; y <= R; y++) {
                if (judge(u, x, y))
                    ans.push_back(u + point(x, y));
            }
        }

        sort(ans.begin(), ans.end());
        printf("%lu", ans.size());
        for (int i = 0; i < ans.size(); i++)
            printf(" (%d,%d)", ans[i].x, ans[i].y);
        printf("\n");
    }
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        init();
        solve();
    }
    return 0;
}