题解：CF257C View Angle

Adventurer_XIV / 2024-08-07 / 原文

题目传送门

题意

平面上有 $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;
}