尚未完整测试，务必留意模板 bug！
/* Clearink */
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
namespace PCG {
const double PI = acos ( -1. ), EPS = 1e-9, INF = 2e9;
/* treat x as 0 <=> -EPS < x < EPS */
inline double dabs ( const double x ) { return x < 0 ? -x : x; }
inline double dmin ( const double a, const double b ) { return a < b ? a : b; }
inline double dmax ( const double a, const double b ) { return b < a ? a : b; }
inline int dcmp ( const double x, const double y = 0 ) {
return dabs ( x - y ) < EPS ? 0 : x < y ? -1 : 1;
}
struct Point {
double x, y;
inline Point ( const double tx = 0, const double ty = 0 ):
x ( tx ), y ( ty ) {}
inline Point operator + ( const Point& p ) const {
return Point ( x + p.x, y + p.y );
}
inline Point operator - ( const Point& p ) const {
return Point ( x - p.x, y - p.y );
}
inline Point operator - () const {
return Point ( -x, -y );
}
inline Point operator * ( const double v ) const {
return Point ( x * v, y * v );
}
inline Point operator / ( const double v ) const {
return Point ( x / v, y / v );
}
inline double operator * ( const Point& p ) const { // dot.
return x * p.x + y * p.y;
}
inline double operator ^ ( const Point& p ) const { // cross.
return x * p.y - y * p.x;
}
inline bool operator == ( const Point& p ) const {
return !dcmp ( x, p.x ) && !dcmp ( y, p.y );
}
inline bool operator != ( const Point& p ) const {
return !( *this == p );
}
inline bool operator < ( const Point& p ) const { // as a pair (x,y).
return dcmp ( x, p.x ) ? x < p.x : y < p.y;
}
inline double length () const { return sqrt ( *this * *this ); }
inline Point unit () const { return *this / this->length (); }
inline Point normal () const { return Point ( y, -x ); }
inline double angle () const { // [0,2pi).
double t = atan2 ( y, x );
return t < 0 ? t + 2 * PI : t;
}
inline Point rotate ( const double alpha ) const {
double c = cos ( alpha ), s = sin ( alpha );
return Point ( x * c - y * s, y * c + x * s );
}
friend inline double angle ( const Point& p, const Point& q ) { // [0,pi).
double t = atan2 ( p ^ q, p * q );
t < 0 && ( t += 2 * PI, 0 );
return t < PI ? t : 2 * PI - t;
}
friend inline double dist ( const Point& p, const Point& q ) {
return ( p - q ).length ();
}
friend inline double slope ( const Point& p, const Point& q ) {
return dcmp ( p.x, q.x ) ?
( p.y - q.y ) / ( p.x - q.x ) : p.y < q.y ? INF : -INF;
}
inline void read () { scanf ( "%lf %lf", &x, &y ); }
inline void _show ( const char ch = '
' ) const {
#ifdef RYBY
printf ( "(%f, %f)%c", x, y, ch );
#endif
}
};
typedef Point Vector;
struct Line {
Point p, v;
inline Line (): p (), v () {}
inline Line ( Point a, Point b, const bool type = false ):
p ( a ), v ( type ? b - a : b ) {}
inline Line ( const double a, const double b, const double c ):
p ( dcmp ( a ) ? Point ( -c / a, 0 ) : Point ( 0, -c / b ) ),
v ( -b, a ) {}
inline Point A () const { return p; }
inline Point B () const { return p + v; }
inline bool operator < ( const Line& l ) const {
return dcmp ( atan2 ( v.y, v.x ), atan2 ( l.v.y, l.v.x ) ) < 0;
}
inline bool onLeft ( const Point& q ) const {
return dcmp ( v ^ ( q - p ) ) > 0;
}
inline bool onLine ( const Point& q ) const {
return !dcmp ( ( q - p ) ^ v );
}
inline bool onRay ( const Point& q ) const {
return onLine ( q ) && dcmp ( ( q - p ) * v ) >= 0;
}
inline bool onSegment ( const Point& q ) const {
if ( !onLine ( q ) ) return false;
return dcmp ( ( A () - q ) * ( B () - q ) ) <= 0;
}
friend inline bool sameSide ( const Line& l,
const Point& p, const Point& q ) {
return dcmp ( ( ( p - l.p ) ^ ( p - l.B () ) )
* ( ( q - l.p ) ^ ( q - l.B () ) ) ) > 0;
}
friend inline bool interSegment ( const Line& l1, const Line& l2 ) {
return ( !sameSide ( l1, l2.p, l2.B () ) )
&& ( !sameSide ( l2, l1.p, l1.B () ) );
}
friend inline bool interRay ( const Line& l1, const Line& l2 ) {
return dcmp ( ( ( l2.p - l1.p ) ^ l2.v ) / ( l1.v ^ l2.v ) ) > 0
&& dcmp ( ( ( l1.p - l2.p ) ^ l1.v ) / ( l2.v ^ l1.v ) ) > 0;
}
friend inline Point lineInter ( const Line& l1, const Line& l2 ) {
return l1.p + l1.v * ( ( l2.p - l1.p ) ^ l2.v ) / ( l1.v ^ l2.v );
}
};
inline std::vector<Point> getConvex ( std::vector<Point> vec,
const bool allowCol ) {
static std::vector<Point> ret;
ret.resize ( vec.size () << 1 );
std::sort ( vec.begin (), vec.end () );
int n = ( int ) vec.size (), top = 0;
for ( int i = 0; i < n; ++i ) {
for ( int d; top > 1; --top ) {
d = dcmp ( ( ret[top - 1] - ret[top - 2] )
^ ( vec[i] - ret[top - 2] ) );
if ( !( ( !allowCol && d <= 0 ) || ( allowCol && d < 0 ) ) ) break;
}
ret[top++] = vec[i];
}
for ( int tmp = top, i = n - 2; ~i; --i ) {
for ( int d; top > tmp; --top ) {
d = dcmp ( ( ret[top - 1] - ret[top - 2] )
^ ( vec[i] - ret[top - 2] ) );
if ( !( ( !allowCol && d <= 0 ) || ( allowCol && d < 0 ) ) ) break;
}
ret[top++] = vec[i];
}
if ( n > 1 ) --top;
return ret.resize ( top ), ret;
}
inline bool poleCmp ( const Point& p, const Point& q ) {
static int t;
return ( t = dcmp ( p ^ q ) ) > 0
|| ( !t && dcmp ( p.length (), q.length () ) < 0 );
}
inline Point polyCentroid ( const std::vector<Point>& poly ) {
double area = 0; Point ret;
int n = ( int ) poly.size ();
for ( int i = 0; i ^ poly.size (); ++i ) {
double s = poly[i] ^ poly[( i + 1 ) % n];
area += s;
ret.x += ( poly[i].x + poly[( i + 1 ) % n].x ) * s;
ret.y += ( poly[i].y + poly[( i + 1 ) % n].y ) * s;
}
ret.x /= 3, ret.y /= 3; // triangle's centroid.
ret.x /= area, ret.y /= area; // average.
return ret;
}
inline double polyArea ( const std::vector<Point>& poly ) {
double ret = 0; int n = ( int ) poly.size ();
for ( int i = 0; i < n; ++i ) {
ret += poly[i] ^ poly[( i + 1 ) % n];
}
return dabs ( ret / 2 );
}
inline std::vector<Point> halfPlaneInter ( std::vector<Line> lvec ) {
static std::vector<std::pair<double, int> > ord;
static std::deque<Line> que; que.clear ();
static std::deque<Point> ret; ret.clear ();
lvec.push_back ( Line ( Point ( -INF, -INF ), Point ( 1, 0 ) ) );
lvec.push_back ( Line ( Point ( -INF, INF ), Point ( 0, -1 ) ) );
lvec.push_back ( Line ( Point ( INF, -INF ), Point ( 0, 1 ) ) );
lvec.push_back ( Line ( Point ( INF, INF ), Point ( -1, 0 ) ) );
int n = ( int ) lvec.size (); ord.resize ( n );
for ( int i = 0; i < n; ++i ) {
ord[i].first = atan2 ( lvec[i].v.y, lvec[i].v.x );
ord[i].second = i;
}
std::sort ( ord.begin (), ord.end () );
que.push_back ( lvec[ord[0].second] );
for ( int i = 1; i < n; ++i ) {
const Line& l ( lvec[ord[i].second] );
for ( ; que.size () > 1 && !l.onLeft ( ret.back () );
que.pop_back (), ret.pop_back () );
for ( ; que.size () > 1 && !l.onLeft ( ret[0] );
que.pop_front (), ret.pop_front () );
if ( dcmp ( l.v ^ que.back ().v ) ) {
que.push_back ( l );
if ( que.size () > 1 ) {
ret.push_back (
lineInter ( que[que.size () - 2], que.back () ) );
}
} else if ( que.back ().onLeft ( l.p ) ) {
que.back () = l;
if ( que.size () > 1 ) {
ret.back () = lineInter ( que[que.size () - 2], que.back () );
}
}
}
for ( ; que.size () > 1 && !que[0].onLeft ( ret.back () );
que.pop_back (), ret.pop_back () );
if ( que.size () <= 2 ) return {};
if ( que.size () > 1 ) ret.push_back ( lineInter ( que[0], que.back () ) );
return std::vector<Point> ( ret.begin (), ret.end () );
}
inline double convexDiameter ( const std::vector<Point>& conv ) {
int n = ( int ) conv.size ();
if ( n == 1 ) return 0;
if ( n == 2 ) return dist ( conv[0], conv[1] );
double ret = 0;
for ( int i = 0, j = 2; i < n; ++i ) {
for ( ; dabs ( ( conv[j] - conv[i] )
^ ( conv[( i + 1 ) % n] - conv[i] ) )
< dabs ( ( conv[( j + 1 ) % n] - conv[i] )
^ ( conv[( i + 1 ) % n] - conv[i] ) ); j = ( j + 1 ) % n );
ret = dmax ( ret, dmax ( dist ( conv[i], conv[j] ),
dist ( conv[( i + 1 ) % n], conv[j] ) ) );
}
return ret;
}
inline int findPole ( const std::vector<Point>& vec ) {
int ret = -1, n = ( int ) vec.size ();
for ( int i = 0; i < n; ++i ) {
if ( !~ret || dcmp ( vec[ret].y, vec[i].y ) > 0
|| ( !dcmp ( vec[ret].y, vec[i].y )
&& dcmp ( vec[ret].x, vec[i].x ) > 0 ) ) {
ret = i;
}
}
return ret;
}
inline void getPoleOrdered ( std::vector<Point>& conv ) {
int pid = findPole ( conv ), n = ( int ) conv.size ();
pid = n - pid - 1; // reversed.
std::reverse ( conv.begin (), conv.end () );
std::reverse ( conv.begin (), conv.begin () + pid + 1 );
std::reverse ( conv.begin () + pid + 1, conv.end () );
}
inline std::vector<Point> convexSum ( std::vector<Point> A,
std::vector<Point> B ) {
static std::vector<Point> ret; ret.clear ();
getPoleOrdered ( A ), getPoleOrdered ( B );
// if use `getConvexG`, there's no need to `getPoleOrdered`.
int n = ( int ) A.size (), m = ( int ) B.size ();
Point ap ( A[0] ), bp ( B[0] );
ret.push_back ( ap + bp );
for ( int i = 0; i < n - 1; ++i ) A[i] = A[i + 1] - A[i];
A[n - 1] = ap - A[n - 1];
for ( int i = 0; i < m - 1; ++i ) B[i] = B[i + 1] - B[i];
B[m - 1] = bp - B[m - 1];
int i = 0, j = 0;
while ( i < n && j < m ) {
ret.push_back ( ret.back ()
+ ( dcmp ( A[i] ^ B[j] ) >= 0 ? A[i++] : B[j++] ) );
}
for ( ; i < n; ret.push_back ( ret.back () + A[i++] ) );
for ( ; j < m; ret.push_back ( ret.back () + B[j++] ) );
return ret;
}
} using namespace PCG;
int n;
std::vector<Point> pos, cnv;
int main () {
/*
example: https://www.luogu.com.cn/problem/P2742
*/
scanf ( "%d", &n ), pos.resize ( n );
for ( int i = 0; i < n; ++i ) pos[i].readn ();
cnv = getConvex ( pos, true ); // also, it could be `getConvex ( pos, false )`.
#ifdef RYBY
for ( auto p: cnv ) p._show ( ' ' );
putchar ( '
' );
#endif
int s = cnv.size ();
double ans = 0;
for ( int i = 0; i < s; ++i ) {
ans += dist ( cnv[i], cnv[( i + 1 ) % s] );
}
printf ( "%.2f
", ans );
return 0;
}
/*
try this data:
5
0 0
0 3
1 2
2 1
3 0
*/