<html>

2021-10-05 18:14

阅读:743

题目链接: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 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 R) return false; return x * x + y * y


评论


亲,登录后才可以留言!