[HDUOJ]7146. Laser (2022杭电多校第1场I题)（计算几何 + 思维）

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