题目链接:Problem - 7146 (hdu.edu.cn)
题目大意 / Problem
二维平面上有n个敌人(都位于整数点的坐标上),能否找到一个点放置一个激光武器(可以发出米字型的激光,敌人遇到激光就被消灭),使得所有敌人都被消灭。能则输出“YES”,否则输出“NO”。
思路 / Thought
首先特判敌人的个数小于等于2的情况,这种情况的答案一定是YES。
当敌人个数大于2时,假设激光武器在第一个敌人身上,判断是否满足条件,如果是就输出YES,否则记录下不符合条件的点pos,并从敌人1和敌人pos分别作米字线,将交点表示出来,应该是有12个交点,分别为(设第一个敌人位置(x1, y1),第pos个敌人位置(x2, y2)):
交点即图中所示蓝色圈出的点。
此时只需要遍历这12个点作为激光武器的位置,并通过O(N)复杂度的遍历方法,判断是否所有点都满足条件即可。如果存在一个点使得所有敌人都被照射到,那么就输出YES,如果遍历完了还没答案,就输出NO。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 5e5 + 9; struct Point { int x, y; }p[maxn]; int N; int getabs(int x){return x < 0 ? -x : x;} bool isok(Point p1, Point p2) { if(p1.x == p2.x || p1.y == p2.y)return true; else if(getabs(p2.y - p1.y) == getabs(p2.x - p1.x))return true; return false; } bool isok_all(Point o) { for(int i = 1;i <= N; ++ i) if(!isok(p[i], o))return false; return true; } void solve() { cin >> N; for(int i = 1;i <= N; ++ i)cin >> p[i].x >> p[i].y; if(N <= 2)return printf("YES\n"), void(); int pos = 0; for(int i = 2;i <= N; ++ i) { if(isok(p[1], p[i]))continue; else { pos = i; break; } } if(pos == 0)return printf("YES\n"), void(); int x1 = p[1].x, y1 = p[1].y, x2 = p[pos].x, y2 = p[pos].y; vector<Point> v; v.push_back({x2, y1}); v.push_back({x1, y2}); v.push_back({(y2 - y1 + x1 + x2) / 2, (x2 - x1 + y1 + y2) / 2}); v.push_back({(y1 - y2 + x1 + x2) / 2, (x1 - x2 + y1 + y2) / 2}); v.push_back({x1 - y1 + y2, y2}); v.push_back({x2 - y2 + y1, y1}); v.push_back({x2 - y1 + y2, y1}); v.push_back({x1 - y2 + y1, y2}); v.push_back({x2, x1 - x2 + y1}); v.push_back({x1, x2 - x1 + y2}); v.push_back({x1, x1 - x2 + y2}); v.push_back({x2, x2 - x1 + y1}); for(auto &i : v) if(isok_all(i))return printf("YES\n"), void(); return printf("NO\n"), void(); } signed main() { ios::sync_with_stdio(0); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING