LuoGuP2742[模板]二维凸包-白红宇

LuoGuP2742[模板]二维凸包

阅读量：5290 次

发布时间：2019-06-14

本文共 3164 字，大约阅读时间需要 10 分钟。

如你所见,这是二维凸包的模板题.

我用的是水平序的\(Andrew\) 算法,是从毒瘤汝佳那里学的.

先按照水平序对点排序.水平序就是先按照\(x\)坐标排序,相同再排\(y\)坐标.

然后从第一个点开始,构造下凸壳.

具体就是每次比较栈顶元素和当前元素组成的向量和栈顶的两个元素组成的向量的位置关系.

能向下就向下,一直到构造完下凸壳.再同理构造上凸壳.两个凸壳接在一起就是一个完整的凸包.

好了讲完了(如果说得不清不楚不要怪我,我写的时候精神状态极差),下面是这题的代码:

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
                
                 #define int long long#define pb push_back#define Vector Pointusing std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}template < class T > inline void write (T x) { static T stk[100] , top = 0 ; if ( x == 0 ) { putchar ('0') ; return ; } if ( x < 0 ) { x = - x ; putchar ( '-' ) ; } while ( x ) { stk[++top] = x % 10 ; x /= 10 ; } while ( top ) { putchar ( stk[top--] + '0' ) ; } putchar ('\n') ; }const int N = 1e4 + 100 ;const double eps = 1e-8 ;int n , cnt ;double ans ;inline int dcmp (double x) { if ( fabs ( x ) < eps ) return 0 ; else if ( x < 0 ) return - 1 ; else return 1 ; }struct Point { double x , y ; Point () {} Point (double _x , double _y) : x ( _x ) , y ( _y ) {} inline Point operator + ( const Point & a ) const { return Point ( a.x + x , a.y + y ) ; } inline Point operator - ( const Point & a ) const { return Point ( a.x - x , a.y - y ) ; } inline Point operator * ( const double a ) const { return Point ( x * a , y * a ) ; } inline bool operator == ( Point b ) { if ( ! dcmp ( x - b.x ) && ! dcmp ( y - b.y ) ) return true ; else return false ; } inline bool operator < (Point a) const { if ( x != a.x ) return x < a.x ; else return y < a.y ; }} P[N] , t[N] ;inline double dot (Vector a , Vector b) { return a.x * b.x + a.y * b.y ; }inline double cross (Vector a , Vector b) { return a.x * b.y - a.y * b.x ; }inline long double length (Vector a) { return sqrt ( dot ( a , a ) ) ; }inline void Convex (Point * p , Point * tmp) { rep ( i , 1 , n ) { while ( cnt >= 2 && cross ( tmp[cnt] - tmp[cnt-1] , p[i] - tmp[cnt-1] ) <= 0 ) -- cnt ; tmp[++cnt] = p[i] ; } int k = cnt + 2 ; per ( i , n , 1 ) { while ( cnt >= k && cross ( tmp[cnt] - tmp[cnt-1] , p[i] - tmp[cnt-1] ) <= 0 ) -- cnt ; tmp[++cnt] = p[i] ; } return ;}signed main (int argc , char * argv[]) { n = rint () ; rep ( i , 1 , n ) scanf ("%lf%lf" , & P[i].x , & P[i].y ) ; sort ( P + 1 , P + n + 1 ) ; Convex ( P , t ) ; rep ( i , 2 , cnt ) ans += length ( t[i] - t[i-1] ) ; printf ("%.2lf\n" , ans ) ; system ("pause") ; return 0 ;}