uva 1517 - Tracking RFIDs(STL+幾何)

uva 1517 - Tracking RFIDs(STL+幾何)

題目鏈接：uva 1517 - Tracking RFIDs

題目大意：給定S，R，W，P，表示有R個傳感器，感應半徑為R，W堵牆，P個產品，給定S個傳感器的位置，W堵牆的位置（兩端點），以及P個產品的位置。輸出每個產品可以被那些傳感器確定位置。如果傳感器和產品之間隔著k堵牆，則距離要加上k。

解題思路：S個數很大，但是R很小，所以枚舉每個產品周圍坐標加減R的距離范圍內的點，判斷是否存在傳感器，如果存在判斷距離是否滿足，判斷距離的時候要枚舉牆的位置，判斷兩條線段是否相交，利用向量叉積的性質判斷即可。

#include 
#include 
#include 
#include 
#include 

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 line;

int S, R, W, P;
set pset;
vector 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 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;
}