【[Offer收割]编程练习赛14 D】剑刃风暴(半径为R的圆能够覆盖的平面上最多点数目模板)
2023-09-14 09:03:48 时间
【题目链接】:http://hihocoder.com/problemset/problem/1508
【题意】
【题解】
求一个半径为R的圆能够覆盖的平面上的n个点中最多的点数;
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define Mn 2030//平面点集中点数
#define rep1(i,x,y) for (int i = x;i <= y;i++)
const double eps = 1e-9;//精度调高点没跑~
const double pi = acos(-1.0);
#define sqr(x) ((x) * (x))
struct point
{
double x,y;
double friend dis(const point &a,const point &b)
{
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
}p[Mn + 5];
struct alpha
{
double v;
bool flag;
bool friend operator <(const alpha &a,const alpha &b)//排序专用偏序关系
{
return a.v < b.v;
}
}alp[Mn * Mn + 5];//C(N,2)*2的可能交点(可能极角)
int n;
double R;//半径
int main()
{
//freopen("F:\\rush.txt","r",stdin);
cin >> n >> R;
rep1(i,1,n)
cin >> p[i].x >> p[i].y;
int MAX = 0;
rep1(i,1,n)
{
int t = 0;
rep1(j,1,n)
{
if(i == j)
continue;
double theta,phi,D;
D = dis(p[i],p[j]);
if(D > 2.0 * R)//距离超界直接秒杀
continue;
//关键部分
theta = atan2(p[j].y - p[i].y,p[j].x - p[i].x);
if(theta < 0)
theta += 2 * pi;
phi = acos(D / (2.0 * R));
t++;
alp[t].v = theta - phi + 2 * pi;
alp[t].flag = true;
t++;
alp[t].v = theta + phi + 2 * pi;
alp[t].flag = false;
}
sort(alp+1,alp + 1 + t);
int sum = 0;
rep1(j,1,t)
{
if(alp[j].flag)
sum ++;
else
sum --;
if(sum > MAX)
MAX = sum;
}
}
printf("%d\n",MAX + 1);
return 0;
}
相关文章
- ssti模板注入 命令执行_access注入绕过
- 【说站】python GUI编程有哪些模板
- OpenCV 模板匹配 matchTemplate 源码解析
- 手把手一步步教你使用rpcms的模板Hook
- zblog企业展示型主题模板赢天下(Winlee)助力小微企业成长
- Python Django 编程 | 连载 04 - Django 模板
- 个人博客主题模板中怎么插入第三方视频链接
- 如何将 Power BI 模板化,一键构建出一切
- 【C++ 语言】面向对象 ( 模板编程 | 函数模板 | 类模板 )
- 【Kotlin】Kotlin 常用表达式 ( range 范围表达式 | when 条件表达式 | 字符串模板 )
- 150+道测试高频面试题详解汇总(附用例模板)| 极客时间
- Oracle 巡检及管理模板实践(oracle巡检模板)
- 仿服务器端脚本方式的JS模板实现方法
- 常用的jquery模板插件——jQueryBoilerplate介绍