C. Nearest vectors

C. Nearest vectors


출처: Codeforces C. Nearest vectors

SOL)
 각 들어오는 벡터 점들을 atan2(y, x)를 구해 각도를 저장한다.(radian 값)
그 후 각도를 기준으로 소팅을한다. 그러면 기울기가 작은것 부터 순서대로
백터에 담기게 된다.
백터의 첫 번째 각도에 2pi를 더해줘 맨 마지막에 추가를 한다.

구간 차가 가장 작은 것이 답.

소수점이 상당히 세밀하게 계산을 해줘야하므로 long double에 GNU C++로 재출한다..



[-] Collapse

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
const double pi = acosl(-1.0L);
vector<pair<long double, int > > vec;
int main(){
    freopen("input.txt", "r", stdin);
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++){
        int x, y; scanf("%d %d", &x, &y);
        long double rad = atan2l(y, x); //라디안으로 각도가 나옴 (-1, 1)을 넣으면 136도 = 2.356~~rad
        if (rad < 0) rad += 2 * pi;
        vec.push_back(make_pair(rad, i+1));
    }
    sort(vec.begin(), vec.end());
    int ans1, ans2;
    long double mn = 1000000000;
    vec.push_back(make_pair(vec[0].first + 2 * pi, vec[0].second));
    for (int i = 0; i < vec.size() - 1; i++){
        long double bet = abs(vec[i + 1].first - vec[i].first);
        if (bet < mn){
            mn = bet;
            ans1 = vec[i].second;
            ans2 = vec[i+1].second;
        }
    }
    printf("%d %d", ans1, ans2);
}