Codeforces 598C. Nearest vectors[고정밀 형상]

C. Nearest vectors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.
Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.
Input
First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.
The i-th of the following n lines contains two integers xi and yi (|x|, |y| ≤ 10 000, x2 + y2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).
Output
Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.
Examples
input

4
-1 0
0 -1
1 0
1 1

output

3 4

input

6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

output

6 5

/*
      ： n  ,             ,             ,       
      ：  
      ：                . atan2(y,x)        x      ,    ,
                   ,        (   )      (   )         ,   2*PI
*/

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
const long double PI = acos(-1.0);
vector<pair<long double,int> > vec;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        long double x,y;
        cin>>x>>y;
        pair<long double,int> angle;
        angle.first = atan2(y,x);
        angle.second = i+1;
        vec.push_back(angle);
    }
    sort(vec.begin(),vec.end());
    long double ans_angle = 2*PI;
    int ans1 = 0,ans2 = 0;
    for(int i=0;i<n;i++){
        long double tmp = (vec[(i+1)%n].first-vec[i].first);
        if(tmp<0)tmp+=2*PI;
        if(tmp<ans_angle){
            ans_angle = tmp;
            ans1 = vec[i].second;
            ans2 = vec[(i+1)%n].second;
        }
    }
    printf("%d %d
",ans1,ans2);
}

C 언어의 math.h나 C++의 cmath에는 두 개의 구획을 구하는 함수인atan(double x)과atan2(double y,double x)가 있는데 그들이 되돌아오는 값은 호도가 각도로 바뀌어 스스로 처리해야 한다.전자는 정절치(직선의 사율)를 받아들여 협각을 얻을 수 있지만 정절의 규칙성은 본래 두 각도가 있을 수 있지만 하나만 되돌아온다. 왜냐하면 아탄의 값역은 -90~90이다. 즉, 사상한만 처리하기 때문에 일반적으로 그것을 사용하지 않는다.두 번째 atan2(double y, double x) 중 y는 이미 알고 있는 점의 Y 좌표와 같은 x를 대표하고 반환값은 이 점과 원점의 연결선과 x축의 정방향의 협각이다. 그러면 네 개의 상한의 임의적인 상황을 처리할 수 있다. 그의 값역은 -180~180이다. 예를 들어 예1: 경사율은 1의 직선의 협각이다.

cout<<atan(1.0)*180/PI;//45°
cout<<atan2(1.0,1.0)*180/PI;//45°     
cout<<atan2(-1.0,-1.0)*180/PI;//-135°    

뒤에 두 개의 경사율이 모두 1인데 atan은 45도만 구할 수 있어요.
예2: 경사율은 -1의 직선 각도이다

cout<<atan(-1.0)*180/PI;//-45°
cout<<atan2(-1.0,1.0)*180/PI;//-45° y        
cout<<atan2(1.0,-1.0)*180/PI;//135° x        

흔히 사용하는 것은 원점을 구한 직선의 협각이 아니라 종종 한 선의 협각을 구한다. 이것은atan2에 더욱 물 만난 고기와 같다
예를 들어 A(1.0,1.0)B(3.0,3.0)라는 라인의 AB와 x축의 정방향의 협각을 atan2로 표시하는 것은 atan2(y2-y1,x2-x1), 즉 atan2(3.0-1.0,3.0-1.0)이다. 그의 원리는 A점을 원점 B점으로 평이하여 상응하여 B'(x2-x1,y2-y1)점으로 바꾸는 것과 같다. 이렇게 하면 다시 이전의 예3:A(0.0,5.0)B(5.0,10.0) 라인의 AB의 협각으로 돌아가는 것이다.

cout<<atan2(5.0,5.0)*180/PI;//45°