Pagini recente » Borderou de evaluare (job #1842029) | Borderou de evaluare (job #1902716) | Autentificare | Cod sursa (job #3340907) | Cod sursa (job #3339005)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
typedef pair <long double, long double> punct;
const int nmax = 12e4 + 5;
int n;
punct v[nmax];
double det3 (punct a, punct b, punct c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp (punct x, punct y)
{
return det3 (v[1],x,y) < 0;
}
int k = 2, st[nmax];
void convexhull ()
{
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, cmp);
st[1] = 1;
st[2] = 2;
for (int i = 3; i <= n; i++)
{
while (k >= 2 && det3 (v[st[k - 1]], v[st[k]], v[i]) > 0)
k--;
st[++k] = i;
}
reverse (st + 1, st + k + 1);
}
int main ()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
convexhull ();
fout << k << '\n';
for (int i = 1; i <= k; i++)
fout << fixed << setprecision (12) << v[st[i]].x << " " << v[st[i]].y << '\n';
}