首页 > 其他分享 >题解:CF257C View Angle

题解:CF257C View Angle

时间:2024-08-06 20:05:59浏览次数:11  
标签:度数 Angle atan 象限 CF257C 题解 int text

题目传送门

题意

平面上有 \(n\) 个点。从原点引出两条射线,将平面分成两个部分,使其中一个部分覆盖所有的点。求这个部分与原点所夹的角的最小度数。

思路

既然一个部分覆盖了所有的点,那么另一个部分就一个点都没覆盖,那么要让这个部分最优,这两条射线一定经过两个中间没有任何点的点。那么我们就可以先求出所有点与 \(x\) 轴正半轴的夹角度数,再将这些度数排序,可以看出排完序后相邻的两个点间是没有其他点的。

然后我们只需要算出所有相邻点间的度数取最大值即可,但不要忘了这时一个点也没有覆盖的部分的角度,答案还需要用 \(360\) 度再减一下。

那么怎么求角度呢?我们已经知道了这个点的坐标 \((x,y)\),由数学知识可得角度即为 \(\text{arctan}(\frac{y}{x})\)。看到题解区其他大佬用的都是 \(\text{atan2}\) 这个函数求的角度,蒟蒻的我第一反应想到的是 \(\text{atan}\)。

由于 \(\text{atan}\) 返回的是与 \(x\) 轴以弧度为单位的角度,并且当点在一三象限时是正值,在二四象限时是负值,而 \(\text{atan2}\) 返回的是与 \(x\) 轴正半轴以弧度为单位的角度,并且点在 \(x\) 轴上方时为正,在 \(x\) 轴下方时为负。因此当点在二三象限时我们需要对 \(\text{atan}\) 函数返回值进行处理,具体见代码。

代码

#include<bits/stdc++.h>
#define int long long 
#define MAX 100005
using namespace std;
const double p=acos(-1);
int n;
double ans,at[MAX];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1,x,y;i<=n;i++){
		cin>>x>>y;
		at[i]=atan(double(y*1.0/x))*180/p;//弧度不要忘了乘上180/π
		if(x<0&&y==0)at[i]=180;//如果点在x负半轴上,度数为180 
		if(x<0&&y<0)at[i]=at[i]-180;//点在第三象限 
		if(x<0&&y>0)at[i]=at[i]+180;//点在第二象限 
		//如果不理解可以手造几组数据输出一下看看结果 
	}
	sort(at+1,at+1+n);
	ans=360-(at[n]-at[1]);
	for(int i=1;i<=n-1;i++)ans=max(ans,at[i+1]-at[i]);
	cout<<fixed<<setprecision(10)<<360-ans<<'\n';
	return 0;
}

标签:度数,Angle,atan,象限,CF257C,题解,int,text
From: https://www.cnblogs.com/MithrilSwordXIV/p/18345903

相关文章

  • 【题解】暑假集训CSP提高模拟14
    目录Rank&挂分A.BA题目内容部分分10pts10+20pts正解思路代码B.BB题目内容部分分5pts正解思路代码C.BCD.BDRank&挂分T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。A.BA题目内容现在有\(m\)块烙板,\(n\)张饼,第\(i\)张饼需要烙\(a_i\)个单位时间,一张饼一个单位时刻只能......
  • 2024MX-MF-DAY1-text题解
    T1【题目描述】有\(n\)个人按编号从\(1\)到\(n\)坐成一圈,即第\(i\in[1,n]\)个人右边是\(i+1\),第\(n\)个人右边的人是\(1\)。初始,每个人手上有\(m\)个球。随后,\(n\)个人按编号从小到大的顺序依次执行如下操作:把自己手中的球分成数量相同且尽可能多的三份,......
  • AkSoundSeedAir.dll修复指南:游戏音频问题解决与预防技巧
    AkSoundSeedAir.dll是一个与声音引擎相关的动态链接库(DynamicLinkLibrary,简称DLL)文件,尤其与Wwise(AudiokineticWwise)声音设计和游戏音效中间件有关。Wwise是一个广泛应用于游戏开发的声音引擎,用于处理游戏中的音频和音效,AkSoundSeedAir.dll就是Wwise的一部分,用于实现声音处理......
  • 花园改造 题解
    题目id:9989题目描述小\(X\)开始改造她的环形的花园了,具体来说她要在花园的环上种满\(n\)棵树。她现在有\(3\)种树:种子、小树苗和大树。每个位置上种不同的树会产生不同的满意度,具体来说在第\(i\)个位置,种种子会产生\(a_i\)的满意度,种小树苗会产生\(b_i\)的满意度,种大树会产生\(c......
  • [AGC005B] Minimum Sum 题解
    题目传送门看到这道题很多人用单调栈,其实用笛卡尔树本质差不多,但是思维难度更小。不知道笛卡尔树的同学可以看这里简单说来,笛卡尔树的一个子树可以代表一个区间,且左子树上点的下标小于根节点,右子树上点的坐标大于根节点。这道题要求所有子区间的\(\texttt{min}\)值之和,其实......
  • 迟钝的舞会 题解
    题目id:1329题目描述牛是公认的笨拙的舞者。然后,约翰发现富有音乐细胞的母牛能产更多的奶。因此,他把他的整圈的牛都拉进了舞蹈培训班,包括所有的公牛(因为跳舞的时候得一男一女-_-)。这些牛正好有\(n\)头是公的,有\(n\)头是母的。在第一堂课开始之前,舞蹈老师想将他们分成一对一对的(......
  • 08-04 题解
    08-03题解A根据题目的提示,发现所有数的积是不变的(\(gcd(a,b)*lcm(a,b)=a*b\)),所以差大和大简易证明设\(g=gcd(a,b)\),则\(a=a'g,\)\(b=b'g\),\(lcm(a,b)=a'b'g\)\(gcd(a,b)+lcm(a,b)=g(1+a'b')\)\(a+b=g(a'......
  • 08-02 题解
    <head><scriptsrc="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"type="text/javascript"></script><scripttype="text/x-mathjax-config">MathJax.Hub.Co......
  • ARC152C 题解
    blog。可能是很简单的,但是我实在是不会这种神秘题/ll/ll。Conclusion1.记\(d=a_n-a_1\),则极差始终等于\(d\)。证明显然。Conclusion2.操作极值时,最小值始终变化为\(d\),并且可以进行无限次这样的变化。证明显然。题意转变:最小化\((\texttt{最小值}\bmodd)\),且最小......
  • AISING2020E 题解
    blog。没题解就来写一篇捏。显然\(L_i>R_i\)的人都想去左边(记为LFT人),\(L_i<R_i\)的人都想去右边(记为RHT人),\(L_i=R_i\)的人可以摆烂。(LFT人与RHT人互相干扰,很难刻画。于是找性质。)存在最优方案,使得所有LFT人都在RHT人的左边。证明:如果有RHT人在LFT人的左边,......