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

发布于 2022-07-19  630 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-20