<html>
2021-10-05 18:14
题目链接：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
上一篇：c语言extern关键字详解
下一篇：C# 文件操作常用方法总结