#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FOR(i,n) for(int i=0,_n=n;i<_n;i++) #define FORR(i,s,n) for(int i=s,_n=n;i<_n;i++) #define mp make_pair #define pb push_back #define pii pair #define pli pair #define vi vector #define fs first #define sec second #define maxn 100000 using namespace std; typedef long long ll; const ll MOD = 1000000007LL; const double EPS = 1e-12; vector > s; vector >ovojnica; template pair operator-(const pair &l, const pair & r){ return mp(l.fs-r.fs,l.sec-r.sec); } template U v_prod(const pair &l, const pair &r){ return l.fs*r.sec-l.sec*r.fs; } bool po_kotu(paira, pairb){ return v_prod(a-s[0],b-s[0])>EPS; } bool noter(pair p){ FORR(i,1,ovojnica.size()) if(v_prod(ovojnica[i-1]-p,ovojnica[i]-p) r=s[i]; while(ovojnica.size()>2 && v_prod(r-ovojnica.end()[-2],r-ovojnica.end()[-1])