basic geo

#include <bits/stdc++.h>
#define EPS 1e-9
#define PI acos(-1.0)

using namespace std;

double DEG_to_RED(double d){
    return d*PI/180.0;
}

double RED_to_DEG(double d){
    return d*180.0/PI;
}

struct point{
    double x, y;
    point(){
        x = y = 0.0;
    }

    point(double _x, double _y): x(_x), y(_y) {}

    bool operator==(point &other) const{
        return fabs(x-other.x) < EPS && fabs(y-other.y) < EPS;
    }
};

struct vetor{
    double x, y;
    vetor(double _x, double _y): x(_x), y(_y){}
};

vetor toVetor(point a, point b){
    return vetor(b.x-a.x, b.y-a.y);
}

double dist(point a, point b){
    return hypot(a.x-b.x, a.y-b.y);
}

double perimetro(vector<point> &poli){
    double ans = 0.0;
    for(int i = 0; i < poli.size()-1; i++){
        ans += dist(poli[i], poli[i+1]);
    }

    return ans;
}
double area(vector<point> &poli){
    double ans = 0.0;

    for(int i = 0; i < poli.size()-1; i++){
        ans += (poli[i].x*poli[i+1].y -
                poli[i].y*poli[i+1].x);
    }

    return fabs(ans)/2.0;
}

// produto escalar
double pe(vetor a, vetor b){
    return a.x*b.x + a.y*b.y;
}

//produto vetorial
double pv(vetor a, vetor b){
    return a.x*b.y - a.y*b.x;
}

// diz se o ponto o esta a esquerda da linha lr;
// mesma orientação
double inLeft(point o, point l, point r){
    return pv(toVetor(o, l), toVetor(o, r)) > 0;
}
// |v|
double norma(vetor v){
    return v.x*v.x + v.y*v.y;
}

// retorna o angulo AoB
double angulo(point a, point o, point b){
    vetor oa = toVetor(o, a), ob = toVetor(o, b);
    return acos(pe(oa, ob)/sqrt(norma(oa)*norma(ob)));
}

// retorna se o ponto o esta na linha lr
bool colinear(point o, point l, point r){
    return pv(toVetor(o, l), toVetor(o, r)) < EPS;
}

bool isConvex(vector<point> &poli){
    int sz = poli.size();
    if(sz <= 3) return false;
    bool isLeft = inLeft(poli[0], poli[1], poli[2]);
    for(int i = 1; i < sz-1; i++){
        if(inLeft(poli[i], poli[i+1], poli[(i+2) == sz? 1: (i+2)]) != isLeft) return false;
    }

    return true;
}

bool inPolygon(point pt, vector<point> &poli){
    if(poli.size() == 0) return false;
    double sum = 0;
    for(int i = 0; i < poli.size()-1; i++){
        if(inLeft(pt, poli[i], poli[i+1])){
            sum += angulo(poli[i], pt, poli[i+1]);
        }else sum -= angulo(poli[i], pt, poli[i+1]);
    }

    return fabs(fabs(sum)-2*PI) < EPS;
}

point pivot;
bool compare(point a, point b){
    if(colinear(pivot, a, b)){
        return dist(pivot, a) < dist(pivot, b);
    }

    double pax = a.x-pivot.x, pay = a.y-pivot.y;
    double pbx = b.x-pivot.x, pby = b.y-pivot.y;

    return (atan2(pay,pax)-atan2(pby, pbx)) < 0;
}
vector<point> CH(vector<point> &poli){
    int n = poli.size();
    if(n <= 3){
        if(!(poli[0] == poli[n-1])) poli.push_back(poli[0]);
        return poli;
    }

    // acha o melhor ponto
    // o menor Y com o maior X
    int ini = 0;
    for(int i = 0; i < n; i++){
        if(poli[i].y < poli[ini].y ||
           ((poli[i].y == poli[ini].y) && poli[i].x > poli[ini].x)) ini = i;
    }

    point aux = poli[0];
    poli[0] = poli[ini];
    poli[ini] = aux;

    pivot = poli[0];
    sort(++poli.begin(), poli.end(), compare);

    vector<point> ans;
    ans.push_back(poli[n-1]);
    ans.push_back(poli[0]);
    ans.push_back(poli[1]);

    int idx = 2;
    while(idx < n){
        int last = ans.size()-1;
        if(inLeft(ans[last-1], ans[last], poli[idx])){
            ans.push_back(poli[idx++]);
        }else ans.pop_back();
    }

    return ans;
}
int main(){
    return 0;
}