Pagini recente » Cod sursa (job #3139027) | Cod sursa (job #1555174) | Cod sursa (job #1667113) | Cod sursa (job #162739) | Cod sursa (job #2253920)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define point pair<double,double>
#define nmax 200010
point v[nmax], a[nmax];
int n, nr;
double delta(point a, point b, point c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-(a.y*b.x+b.y*c.x+c.y*a.x);
}
int vf(const point p1,const point p2)
{
return delta(v[1], p1, p2) > 0;
}
void convex()
{
int poz = 1;
for(int i = 2; i <= n; ++i)
{
if(v[i] < v[poz])
poz = i;
}
swap(v[1], v[poz]);
sort(v+2, v+n+1, vf);
a[1] = v[1];
a[2] = v[2];
nr = 2;
for(int i = 3; i <= n; ++i)
{
while(delta(a[nr-1], a[nr], v[i])<=0)
nr--;
a[++nr] = v[i];
}
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
convex();
fout << nr << '\n';
for(int i = 1; i <= nr; ++i)
{
fout << fixed << setprecision(6) << a[i].x <<' '<< a[i].y <<'\n';
}
return 0;
}