CFR 598 C. Nearest vectors ( atan2 )

Problem - 598C - Codeforces

題意：
給 N 個非零向量，求任意一對夾角最小的向量對。

資料規模：
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;
}