Pagini recente » Cod sursa (job #1615397) | Cod sursa (job #1518467) | Cod sursa (job #1554838) | Cod sursa (job #2323518) | Cod sursa (job #883371)
Cod sursa(job #883371)
# include <cstdio>
# include <fstream>
# include <algorithm>
# include <iomanip>
using namespace std;
ofstream g ("infasuratoare.out");
# define x first
# define y second
const int Nmax = 120005;
typedef pair<double, double> nod;
int n, nr;
nod v[Nmax], sol[Nmax];
double verif_convex(nod a, nod b, nod c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int cmp(nod a, nod b) {
return verif_convex(v[1], a, b) < 0;
}
void citire ()
{
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf ("%lf%lf", &v[i].x, &v[i].y);
}
}
void afisare ()
{
g << fixed;
g << nr << '\n';
for (int i = nr; i > 0; --i)
g << setprecision(9) <<sol[i].x << ' ' << sol[i].y << '\n';
g.close ();
}
void sortare ()
{
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);
}
void infasuratoare_convexa ()
{
sortare ();
sol[1] = v[1];
sol[2] = v[2];
nr = 2;
for (int i = 3; i <= n; ++i)
{
while (verif_convex(sol[nr-1], sol[nr], v[i]) > 0)
--nr;
sol[++nr] = v[i];
}
}
int main ()
{
citire ();
infasuratoare_convexa ();
afisare ();
return 0;
}