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