题意
平面上有 \(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