# 计算几何模板（部分，以后更新）

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

const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 1010;

int cmp(double x) {
if (fabs(x) < eps) return 0;
if (x > 0) return 1;
return -1;
}

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

struct point {
double x, y;
point() {}
point(double a, double b) : x(a), y(b) {}
void input() {
scanf("%lf%lf", &x, &y);
}
friend point operator + (const point& a, const point& b) {
return point(a.x+b.x, a.y+b.y);
}
friend point operator - (const point& a, const point& b) {
return point(a.x-b.x, a.y-b.y);
}
friend bool operator == (const point& a, const point& b) {
return cmp(a.x-b.x)==0 && cmp(a.y-b.y)==0;
}
friend point operator * (const point& a, const double& b) {
return point(a.x*b, a.y*b);
}
friend point operator * (const double& a, const point& b) {
return point(a*b.x, a*b.y);
}
friend point operator / (const point& a, const double& b) {
return point(a.x/b, a.y/b);
}
double norm() {
return sqrt(sqr(x)+sqr(y));
}
};

double det(const point& a, const point& b) {
return a.x*b.y-a.y*b.x;
}

double dot(const point& a, const point& b) {
return a.x*b.x+a.y*b.y;
}

double dist(const point& a, const point& b) {
return (a-b).norm();
}

point rotate_point(const point& p, double A) {
double tx = p.x, ty = p.y;
return point(tx*cos(A)-ty*sin(A), tx*sin(A)+ty*cos(A));
}

struct polygon_convex {
vector<point> P;
polygon_convex(int Size = 0) {
P.resize(Size);
}
};

bool comp_less(const point& a, const point& b) {
return cmp(a.x-b.x)<0 || (cmp(a.x-b.x)==0 && cmp(a.y-b.y) < 0);
}

polygon_convex convex_hull(vector<point> a) {
polygon_convex res(2*a.size()+5);
sort(a.begin(), a.end(), comp_less);
a.erase(unique(a.begin(), a.end()), a.end());
int m = 0;
for (int i = 0; i < int(a.size()); ++i) {
while (m > 1 && cmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2])) <= 0)
--m;
res.P[m++] = a[i];
}
int k = m;
for (int i = int(a.size())-2; i >= 0; --i) {
while (m > k && cmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2]) <= 0))
--m;
res.P[m++] = a[i];
}
res.P.resize(m);
if (a.size() > 1)
res.P.resize(m-1);
return res;
}

int main() {

return 0;
}