题目链接：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; }