CFR 613 A. Peter and Snow Blower ( Geometry )

Problem - A - Codeforces

題意：
給一個代表自轉中心的座標，以及順時針給的座標描述一個凸多邊形。問旋轉 360 度後，被覆蓋過的面積有多少。

資料規模：
N ≤ 1e5

解法：
顯然要找離圓心的最遠點，以及最近點... 但仔細想想會發現不是最近點，其實是和任意線段的最近距離。
點和線段的最近距離可以分成兩種情形討論：
1. 最近點在線段端點
2. 最近點在該點在線段的投射處
假設我們要求的是點 P 到 AB 線段第二種情形的最近距離
那麼求叉積 xaji = A->P • A->B
在求投影線段長 len = xaji / | A->B |
那麼就能求出投影點座標為：
( A.x + ( A->B ).x * len / | A->B |, A.y + ( A->B ).y * len / | A->B | )

時間 / 空間複雜度：
O( N )

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

const int MAXN = ( int ) 1e5;

int N, sx, sy;
int X[ MAXN ], Y[ MAXN ];

double sqr( double x ){
  return x * x;
}

double dis( double x1, double y1, double x2, double y2 ){
  return sqrt( sqr( x1 - x2 ) + sqr( y1 - y2 ) );
}

double length( pair< double, double > p ){
  return sqrt( sqr( p.first ) + sqr( p.second ) );
}

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> sx >> sy;
    for( int i = 0; i < N; ++i ){
      cin >> X[ i ] >> Y[ i ];
    }
  }
  {
    double maxr = 0.0, minr = 1e9;
    for( int i = 0; i < N; ++i ){
      maxr = max( maxr, dis( sx, sy, X[ i ], Y[ i ] ) );
      int j = ( i + 1 ) % N;
      minr = min( minr, dis( sx, sy, X[ i ], Y[ i ] ) );
      pair< double, double > zs = make_pair( sx - X[ i ], sy - Y[ i ] );
      pair< double, double > zp = make_pair( X[ j ] - X[ i ], Y[ j ] - Y[ i ] );
      double xaji = zs.first * zp.first + zs.second * zp.second;
      double len = fabs( xaji / length( zp ) );
      if( len >= length( zp ) ) continue;
      pair< double, double > m = make_pair( zp.first * len / length( zp ),
                                            zp.second * len / length( zp ) );
      minr = min( minr, dis( sx, sy, X[ i ] + m.first, Y[ i ] + m.second ) );
    }
    double ans = ( sqr( maxr ) - sqr( minr ) ) * acos( -1.0 );
    cout << fixed << setprecision( 9 ) << ans << endl;
  }
  return 0;
}