问题 D 视线

借鉴大佬:
https://www.cnblogs.com/albert-biu/p/10907996.html
对已有的代码进行详细解释
问题:
在这里插入图片描述
在这里插入图片描述如图所示
如果两个点可见的话,那么这两个点在圆上的四个切点存在公共区域,即图一和图二两种情况,所以只需要求出每一个点在圆上的两个切点(用弧度表示,范围【0 , 2*pi】),然后对于这些点进行排序,遍历每一对切点,找他们中间有多少个点,计算出来的结果除以二,为最后答案 即:ans=(∑(0,n) ai)/2

注意:

  1. atan() 与 atan2() 的区别 第一个范围(-90,90) 第二个范围(-180,180)
  2. 后边的计算中加上 2pi 为了把范围定位到(0,2pi)

在这里插入图片描述
4.lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100010;
const double pi=acos(-1);
struct point
{
    double x,y;
}a[maxn];
struct node
{
    double begin,end;
}e[maxn];
vector<double>s;
int main()
{
    int n;
    double r;
    cin>>n>>r;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x>>a[i].y;
        double len=sqrt(a[i].x*a[i].x+a[i].y*a[i].y);
        double r1=acos(r/len);
        double r2=atan2(a[i].y,a[i].x);
        //注意3
        e[i].begin=r2-r1+2*pi;
        e[i].end=r2+r1+2*pi;
        if(e[i].begin-2*pi>=0) e[i].begin-=2*pi;
        if(e[i].end-2*pi>=0) e[i].end-=2*pi;
        if(e[i].end-e[i].begin<=0) swap(e[i].end,e[i].begin);
        //
        s.push_back(e[i].begin);
        s.push_back(e[i].end);
    }
    long long ans=0;
    sort(s.begin(),s.end());
    long long from,to;
    for(int i=0;i<n;i++)
    {
        from=lower_bound(s.begin(),s.end(),e[i].begin)-s.begin();
        to=lower_bound(s.begin(),s.end(),e[i].end)-s.begin();
        if(e[i].end-e[i].begin-pi>=0)
        {
            ans=ans+2*n-(to-from-1)-2;
        }
        else
        {
            ans+=to-from-1;
        }
    }
    cout<<ans/2<<endl;
    return 0;
}


版权声明:本文为flymoyu原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/flymoyu/article/details/90478085

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...