struct point {
   long double x,y;

};

struct Vector {
    long double x,y;
    Vector() = default;
    Vector (int x,int y): x(x),y(y) {}
    Vector operator * (int b) { return Vector(x*b,y*b); }
    Vector operator + (Vector v2) {return Vector(x+v2.x,y+v2.y); }
};

struct line {
    long double a,b,c;
    line (point p1, point p2) {
        a = p1.y - p2.y;
        b = p2.x - p1.x;
        c = -a*p1.x - p1.y*b;
    }
};

struct segment {
    point a,b;
    segment (point q, point w) {
        a=q;
        b=w;
    }
};

void printPoint (point p) {
    cout<<p.x<<" "<<p.y<<"\n";
}

void printVector (Vector p) {
    cout<<p.x<<" "<<p.y<<"\n";
}

long double vectorLength(Vector a) {
    return sqrt(a.x*a.x+a.y*a.y);
}

long double pointDist (point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

long double dotproduct (Vector a, Vector b) {
    return a.x*b.x + a.y*b.y;
}
long double crossproduct (Vector a, Vector b) {
    return a.x*b.y - a.y*b.x;
}
bool cmp (point a, point b) {
	return a.x < b.x || a.x == b.x && a.y < b.y;
}

bool cw (point a, point b, point c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw (point a, point b, point c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void convex_hull (vector<point> & a) { //PLEASE LOOK HERE
	if (a.size() == 1)  return;
	sort (a.begin(), a.end(), &cmp);
	point p1 = a[0];
	point p2 = a.back();
	vector <point> up, down;
	up.push_back (p1);
	down.push_back (p1);
	for (int i=1;i<a.size();i++) {
		if (i == a.size()-1 || cw (p1, a[i], p2)) {
			while (up.size() >= 2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
				up.pop_back();
			up.push_back (a[i]);
		}
		if (i == a.size()-1 || ccw (p1, a[i], p2)) {
		while (down.size() >= 2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
		down.pop_back();
		down.push_back (a[i]);
		}
	}
	a.clear();
	for (int i=0;i<up.size();++i)
	a.push_back (up[i]);
	for (int i=down.size()-2;i>0;i--)
	a.push_back (down[i]);
}