В этой теме нет ответов

[yanush]

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <math.h>
using namespace std;
struct point {
long double x,y;
int num;
point (double a,double B)/>{x = a; y = b;}
point (){x = 0; y = 0;}
point operator+(const point p){ point z(0,0); z.x = x + p.x; z.y = y + p.y; return z;}
point operator-(const point p){ point z(0,0); z.x = x - p.x; z.y = y - p.y; return z;}
double operator*(const point p){  return sqrt((p.x-x)*(p.x-x) + (p.y-y)*(p.y-y));}
};
point x[500000],ma(10000000000,0),mb(-10000000000,0);
vector <point > ans,a,b,s;int n;
long double sqr(point x1,point x2,point x3)
{
return (x2.x - x1.x)*(x3.y - x1.y ) - (x2.y - x1.y)*(x3.x - x1.x);
}
bool comp(point a,point B)/>
{
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
freopen("hullp.in","r",stdin);
freopen("hullp.out","w",stdout);
cin >> n;
for(int i(0);i<n;i++)
{
  cin >> x[i].x >> x[i].y;
  x[i].num = i;
  if(x[i].x < ma.x || (x[i].x == ma.x && ma.y > x[i].y))
   ma = x[i];
  if(x[i].x > mb.x || (x[i].x == mb.x && mb.y < x[i].y))
   mb = x[i];
}
for(int i(0);i<n;i++)
{
  if(i == ma.num || i == mb.num) continue;
  if(sqr(ma,mb,x[i]) == 0) continue;
  if(sqr(ma,mb,x[i]) < 0) a.push_back(x[i]);
  else b.push_back(x[i]); 
}
a.push_back(ma);b.push_back(ma);
a.push_back(mb);b.push_back(mb);
sort(a.begin(),a.end(),comp);
sort(b.begin(),b.end(),comp);
ans.push_back(b[0]);ans.push_back(b[1]);
for(int i(2);i<b.size();i++)
{
  int z = ans.size();
  double g = sqr(ans[z-2],ans[z-1],b[i]);
   while(ans.size() > 1 && sqr(ans[ans.size()-2],ans[ans.size()-1],b[i]) >= 0)
	ans.pop_back();
   ans.push_back(b[i]);
}
s.push_back(a[0]);s.push_back(a[1]);
for(int i(2);i<a.size();i++)
{
  while(s.size() > 1 && sqr(s[s.size()-2],s[s.size()-1],a[i])<= 0)
   s.pop_back();
  s.push_back(a[i]);
}
for(int i(s.size()-2);i>0;i--)
  ans.push_back(s[i]);
}