Pagini recente » Cod sursa (job #588940) | Cod sursa (job #184851) | Cod sursa (job #1561130) | Cod sursa (job #2456347) | Cod sursa (job #1519831)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
struct point
{
ld x,y;
};
typedef point pp;
struct ConvexHull
{
vector<pp> hull;
int m;
ConvexHull(): m(0) {hull.clear();}
bool ccw(pp x, pp y, pp z)
{
return ( (y.x-x.x)*(z.y-x.y) > (y.y - x.y)*(z.x - x.x));
}
void MakeHull(int n, pp a[])
{
hull.clear();
if (!n) return;
int x=0;
for (int i=0; i<n; i++)
if ( (a[i].y==a[x].y)?a[i].x<a[x].x:a[i].y<a[x].y)
x=i;
swap(a[0],a[x]);
hull.push_back({a[0].x-1,a[0].y});
hull.push_back(a[0]);
sort(a+1,a+n,[=](pp x, pp y){ return ccw(a[0],x,y); });
m = 1;
for (int i=1; i<n; i++)
{
while (!ccw(hull[m-1],hull[m],a[i]))
if (m>1) hull.pop_back(),m--;
else if (i+1==n) break;
else i++;
hull.push_back(a[i]);
m++;
}
hull.erase(hull.begin());
}
};
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pp v[120001];
ConvexHull cw;
int main()
{
fin>>n;
for (int i=0; i<n; i++)
{
pp x;
fin>>x.x>>x.y;
v[i]=x;
}
cw.MakeHull(n,v);
fout<<cw.m<<'\n';
for (int i=0; i<cw.m; i++)
fout<<setprecision(9)<<fixed<<cw.hull[i].x<<' '<<cw.hull[i].y<<'\n';
return 0;
}