#include<cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>

using namespace std;

#ifndef PI
#define PI 3.14159265358979323846
#endif
#define ABS(x) (((x)<0)?(-(x)):(x))
#define SQR(x) ((x)*(x))

typedef long double ptype;
const ptype p_EPS = (ptype(1e-9));
const double d_EPS = (1e-9);

struct point {
  ptype x, y;
  point(ptype _x=0, ptype _y=0) { x = _x; y = _y; }
  point operator+(point p) { return point(x+p.x,y+p.y); }
  point operator-(point p) { return point(x-p.x,y-p.y); }
  point operator*(ptype k) { return point(x*k,y*k); }
  point operator/(ptype k) { return point(x/k,y/k); }
  ptype operator*(point p) { return x*p.x + y*p.y; }
  ptype operator^(point p) { return x*p.y - y*p.x; }
};
bool operator==(point p1, point p2) {
  return ABS(p1.x-p2.x) <= p_EPS && ABS(p1.y-p2.y) <= p_EPS;
}
ptype sqr_mag(point p) { return p*p; }
double mag(point p) { return sqrt(p*p); }
point unit(point p) { return p/mag(p); }

ostream& operator<<(ostream& os, point p) {
  os << "(" << p.x << "," << p.y << ")";
}

// Distance from point to a line
double linepointdist(point A, point B, point C, bool seg) {
  double ret = ((B-A)^(C-A))/mag(B-A);
  if(seg) {
    if((C-B)*(B-A) > p_EPS) return mag(B-C);
    if((C-A)*(A-B) > p_EPS) return mag(A-C);
  }
  return fabs(ret);
}

// Find the point of intersection of two lines (or line segments)
// LINE_ERROR is set upon no intersection, or parrallel lines
bool LINE_ERROR;
point lineintersect(point W, point X, point Y, point Z, bool seg) {
  point ret;
  ptype A[2], B[2], C[2], det;
  LINE_ERROR = false;
  A[0] = X.y - W.y;  B[0] = W.x - X.x; C[0] = A[0]*X.x + B[0]*X.y;
  A[1] = Z.y - Y.y;  B[1] = Y.x - Z.x; C[1] = A[1]*Y.x + B[1]*Y.y;
  det = A[0]*B[1] - A[1]*B[0];
  if(ABS(det) <= p_EPS) { LINE_ERROR = true; return point(0,0); }
  ret.x = (B[1]*C[0] - B[0]*C[1])/det;
  ret.y = (A[0]*C[1] - A[1]*C[0])/det;
  if(seg) {
    if(min(W.x,X.x)-p_EPS > ret.x || ret.x > max(W.x,X.x)+p_EPS) LINE_ERROR = true;
    if(min(W.y,X.y)-p_EPS > ret.y || ret.y > max(W.y,X.y)+p_EPS) LINE_ERROR = true;
    if(min(Y.x,Z.x)-p_EPS > ret.x || ret.x > max(Y.x,Z.x)+p_EPS) LINE_ERROR = true;
    if(min(Y.y,Z.y)-p_EPS > ret.y || ret.y > max(Y.y,Z.y)+p_EPS) LINE_ERROR = true;
    if(LINE_ERROR) return point(0,0);
  }
  return ret;
}

// Return the angle between A and B, in the range (-PI, PI]
// B unspecified returns the angle A makes with the positive x-axis
double angle(point A, point B = point(ptype(1.0), ptype(0.0))) {
  double theta1, theta2, ret;
  theta1 = atan2(A.y, A.x);
  theta2 = atan2(B.y, B.x);
  ret = theta2 - theta1;
  while(ret > PI) ret -= 2.0*PI;
  while(ret < -PI) ret += 2.0*PI;
  if(ABS(ret + PI) <= d_EPS) return PI;
  return ret;
}

// Determine whether a point lies inside (or on) a polygon
bool inside_polygon(vector<point> poly, point p) {
  double sum = 0.0;
  int n = poly.size();
  point A, B;
  for(int i = 0; i < n; i++) {
    A = poly[i]; B = poly[(i+1)%n];
    if(linepointdist(A, B, p, true) < d_EPS) return true;
    sum += angle(A - p, B - p);
  }
  return (ABS(sum) > PI);
}

// Determine whether a point lies inside (or on) a given convex polygon
bool inside_convex(vector<point> hull, point p) {
  ptype cross;
  for(int i = 0; i < hull.size(); i++) {
    cross = (hull[(i+1)%hull.size()] - hull[i])^(p - hull[i]);
    if(ABS(cross) <= p_EPS) {
      return linepointdist(hull[i],hull[(i+1)%hull.size()],p,true) <= d_EPS;
    }
    if(cross > p_EPS) return false;
  }
  return true;
}

// Area of a polygon
double area_polygon(vector<point> poly) {
  double ret = 0.0;
  for(int i = 1; i + 1 < poly.size(); i++)
    ret += (poly[i]-poly[0])^(poly[i+1]-poly[0]);
  return ABS(ret) / 2.0;
}

// Perimeter of a polygon
double perimeter_polygon(vector<point> poly) {
  double ret = 0.0;
  for(int i = 0; i < poly.size(); i++)
    ret += mag(poly[i]-poly[(i+1)%poly.size()]);
  return ret;
}


// Find the convex hull of a set of points
// vert == true - ONLY vertces
// vert == false - ALL points on the hull
bool point_cmp(point p1, point p2) {
  return (p1.x+p_EPS<p2.x) || (ABS(p1.x-p2.x)<=p_EPS && p1.y+p_EPS<p2.y);
}
vector<point> convex_hull(vector<point> p, bool vert = true) {
  vector<point> hull(0);
  int nh = -1, start = 0;
  ptype cross;
  sort(p.begin(), p.end(), point_cmp);
  p.erase(unique(p.begin(),p.end()),p.end());
  for(int i = 0; i < p.size(); i++) {
    while(nh - start > 0) {
      cross = (p[i]-hull[nh-1])^(hull[nh]-hull[nh-1]);
      if(cross < -p_EPS || (vert && ABS(cross) <= p_EPS)) {
        hull.pop_back();
        nh--;
      } else break;
    }
    hull.push_back(p[i]); nh++;
  }
  start = nh;
  for(int i = p.size()-2; i >= 0; i--) {
    while(nh - start > 0) {
      cross = (p[i]-hull[nh-1])^(hull[nh]-hull[nh-1]);
      if(cross < -p_EPS || (vert && ABS(cross) <= p_EPS)) {
        hull.pop_back();
        nh--;
      } else break;
    }
    hull.push_back(p[i]); nh++;
  }
  if(hull.size() > 1) hull.pop_back();
  return hull;
}

// Circumcentre of A, B and C
// if A,B,C colinear, returns the midpoint of the linesegment
point circumcentre(point A, point B, point C) {
  ptype a,b,c,d,e,f,det;
  a = -2 * (A.x-B.x);
  b = -2 * (A.y-B.y);
  c = SQR(B.x) - SQR(A.x) + SQR(B.y) - SQR(A.y);//B*B-A*A
  d = -2 * (A.x-C.x);
  e = -2 * (A.y-C.y);
  f = SQR(C.x) - SQR(A.x) + SQR(C.y) - SQR(A.y);//C*C-A*A
  det = a*e-b*d;
  if(ABS(det) <= p_EPS) {
    ptype x1, x2, y1, y2;
    x1 = max(max(A.x,B.x),C.x);
    x2 = min(min(A.x,B.x),C.x);
    y1 = max(max(A.y,B.y),C.y);
    y2 = min(min(A.y,B.y),C.y);
    return point((x1+x2)/2,(y1+y2)/2);
  }
  point ret((c*e-f*b)/det,(a*f-d*c)/det);
  return ret;
}


int main() {
 point a(0, 1), b(0,10), c(-1,-1), d(45, 56), e(-10,0);
/*  cout << a+b << " " << a-b << endl;
 cout << linepointdist(a,b,b+b-a,true) << endl;
 cout << linepointdist(a,b,b+b-a,false) << endl;
 cout << p_EPS << endl;
 cout << d_EPS << endl;
 cout << lineintersect(a,b,b,b+b-a,false) << " "; cout << LINE_ERROR << endl;
 cout << lineintersect(a,b,b,b+b-a,true) << " "; cout << LINE_ERROR << endl;
 cout << b*3.12 << endl;
 cout << sqr_mag(unit(d)) << endl;
 cout << angle(a) << endl;
 cout << angle(b) << endl;
 cout << angle(c) << endl;
 cout << angle(d) << endl;
 cout << angle(e) << endl;*/
 vector<point> poly, hull;/*
 poly.push_back(point(0,0));
 poly.push_back(point(0,0.5));
 poly.push_back(point(0,1));
 poly.push_back(point(1,1));
 poly.push_back(point(1,0));*//*
 cout << (inside_polygon(poly, point(0,0))?"YES":"NO") << endl;
 cout << (inside_polygon(poly, point(0,1))?"YES":"NO") << endl;
 cout << (inside_polygon(poly, point(0.5,0.5))?"YES":"NO") << endl;
 cout << (inside_polygon(poly, point(-1,0))?"YES":"NO") << endl;
 cout << (inside_polygon(poly, point(0.25,0.5))?"YES":"NO") << endl;
 cout << area_polygon(poly) << endl;
*/
 for(int i = 0; i < 100; i++)
   poly.push_back(point(rand()*((rand()&1)?-1:1),rand()*((rand()&1)?-1:1)));
 cout << "DONE GENERATING" << endl;
 hull = convex_hull(poly);
 for(int i = 0; i < hull.size(); i++) cout << hull[i] << " ";
 cout << endl;
 cout << perimeter_polygon(hull) << endl;
 cout << area_polygon(hull) << endl;
 for(int i = 0; i < poly.size(); i++) {
   if(!inside_polygon(hull, poly[i])) cout << "ERROR1: " << poly[i] << endl;
   if(!inside_convex(hull, poly[i])) cout << "ERROR2: " << poly[i] << endl;
 }
 for(int i = 0; i < 1000000; i++) {
   point p(rand()*((rand()&1)?-1:1),rand()*((rand()&1)?-1:1));
   if(inside_polygon(hull, p)^inside_convex(hull, p))
     cout << "ERROR: " << p << endl;
 }
 return 0;
}