CFR 613 A. Peter and Snow Blower ( Geometry )
題意:
給一個代表自轉中心的座標,以及順時針給的座標描述一個凸多邊形。問旋轉 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; }