ErikTse Runtime

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

ICPC澳门站 C - Laser Trap(计算几何)

2022年4月4日 984点热度 0人点赞 0条评论

题目链接:C-Laser Trap_第46屆ICPC 東亞洲區域賽(澳門)(正式賽) (nowcoder.com)

题目大意

T个测试用例,二维平面上N个点,形成的完全图。

问至少删除多少个点可以使得一个球在不碰到任何线的情况下从(0, 0)移动到(inf, inf)。

数据保证不存在任何一条线通过(0, 0)。

思路

哎,当时在赛场上想到了用斜率,用atan,也用了long double,但是没想到用atan2l(y, x)这个函数啊!这里需要学习一下这个新函数。

atan2l((long double)y, (long double)x),返回值为long double,表示tan值为y / x的弧度,并且可以表示象限。注意如果本题用double会导致精度不够。

我们将N个点拓展成2 * N点,因为这里的点的顺序并非“偏序”的,举个例子,第二圈的第一象限的角度应该比第一圈第四象限的大,但是第一圈的第一象限的角比第一圈的第四象限的小。

也就是说我们要把每个点,都生成一个“位于第二圈的该点”,使得这个点可以比后面的一些点大,从而避免出现误差。

后面就用双指针来遍历一遍就行了,时间复杂度O(N)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long double PI = acosl(-1);
const int maxn = 2e6 + 9;
 
long double p[maxn];

void solve()
{
	int N;cin >> N;//构造2 * N个点
	//新函数atan2(y, x);可以用于确定某个点的角度,同时可以确定象限
	for(int i = 1;i <= N; ++ i)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		p[i] = atan2l(1.0 * y, 1.0 * x);	
	}
	sort(p + 1,p + 1 + N);
	for(int i = 1;i <= N; ++ i)p[i + N] = p[i] + 2 * PI;
	int ans = N;
	for(int i = 1, j = 1;i <= N; ++ i)
	{
		while(j <= 2 * N && p[j] - p[i] < PI)++ j;
		ans = min(ans, j - i - 1);
	}
	printf("%lld\n",ans);
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ icpc 图论 算法竞赛 计算几何
最后更新:2022年7月9日

Eriktse

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

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

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

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号