ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年7月19日 253点热度 1人点赞 0条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 思维 算法 算法竞赛 计算几何
最后更新:2022年7月20日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号