Codeforces Round 159 (Div. 2) - View Angle 링크
(2023.08.30 기준 Difficulty *1800)

문제

n개의 점이 2차원 좌표로 주어진다. 원점에서 바라볼 때, 모든 점을 포함하는 최소 각도 출력

알고리즘

기하학

풀이

원점에서 바라봐야 하므로 일단은 원점과 각 점 간 절대각을 전부 구하자. 이는 atan2 함수로 구할 수 있다.

자, 아래 gif를 보자.

이처럼 절대각 순으로 정렬한 뒤, 인접한 두 점 사이의 각 차이가 클 수록 나머지 각이 작아진다. 나머지 각에는 모든 점이 포함됨은 당연하므로, 각 차이가 제일 큰 것을 구하여 360도에서 빼서 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1);

double degree(double x, double y){
    return atan2(x, y) * 180 / pi;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 원점과 각 점 간 절대각을 계산하고 정렬
    int n; cin >> n;
    vector<double> angles;
    for (int i = 0, x, y; i < n; i++){
        cin >> x >> y;
        angles.push_back(degree(x, y));
    }
    sort(angles.begin(), angles.end());

    // 제일 큰, 인접한 두 점 간 절대각 차이를 구한다.
    double result = 0;
    for (int i = 0; i < n - 1; i++) result = max(result, angles[i + 1] - angles[i]);
    result = max(result, 360 + angles[0] - angles[n - 1]);

    // 구한 각을 제외한 나머지 각에 모든 점이 포함된다.
    cout << fixed << setprecision(7) << 360 - result;
}

• Python

import sys; input = sys.stdin.readline
from math import atan2, degrees

# 원점과 각 점 간 절대각을 계산하고 정렬
n = int(input())
angles = sorted(degrees(atan2(*tuple(map(int, input().split())))) for _ in range(n))

# 제일 큰, 인접한 두 점 간 절대각 차이를 구한다.
result = 0
for i in range(n - 1):
    result = max(result, angles[i + 1] - angles[i])
result = max(result, 360 + angles[0] - angles[-1])

# 구한 각을 제외한 나머지 각에 모든 점이 포함된다.
print(360 - result)