# CFR 598 C. Nearest vectors ( atan2 )

Problem - 598C - Codeforces

N ≤ 1e5

atan2( y, x ) 回傳的範圍在 [ -pi, pi ] 之間，只有 atan2( 0, 0 ) 是未定義的。

O( N lg N )

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

const int MAXN = int( 1e5 );
const long double PI = acos( -1.0 );

int N;
long double X[ MAXN ], Y[ MAXN ];
int ord[ MAXN ];

long double angle( int i, int j ) {
long double ai = atan2( Y[ i ], X[ i ] );
long double aj = atan2( Y[ j ], X[ j ] );
return min( fabs( ai - aj ), PI * 2 - fabs( ai - aj ) );
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ) {
cin >> X[ i ] >> Y[ i ];
ord[ i ] = i;
}
sort( ord, ord + N, [ & ]( int i, int j ) {
return atan2( Y[ i ], X[ i ] ) < atan2( Y[ j ], X[ j ] ); } );
long double best = angle( ord[ N - 1 ], ord[ 0 ] );
int ans1 = N - 1, ans2 = 0;
for( int i = 0; i + 1 < N; ++i ) {
long double a = angle( ord[ i ], ord[ i + 1 ] );
if( best > a ) {
best = a;
ans1 = i;
ans2 = i + 1;
}
}
cout << ord[ ans1 ] + 1 << " " << ord[ ans2 ] + 1 << endl;
return 0;
}
```