Pagini recente » Cod sursa (job #2510926) | Cod sursa (job #877901) | Cod sursa (job #2980117) | Cod sursa (job #194235) | Cod sursa (job #884237)
Cod sursa(job #884237)
# include <cstdio>
# include <algorithm>
using namespace std;
# define Nmax 120005
# define x first
# define y second
typedef pair<double, double> nod;
nod p[Nmax], stiva[Nmax];
int N, lg;
bool cmp (nod a, nod b)
{
return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
double det(nod a, nod b, nod c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
void infasuratoare_convexa ()
{
sort (p + 1, p + N + 1, cmp);
stiva[1] = p[1];
stiva[2] = p[2];
lg = 2;
for (int i = 3; i <= N; ++i)
{
while (lg >= 2 && det (stiva[lg-1], stiva[lg], p[i]) > 0)
--lg;
stiva[++lg] = p[i];
}
for (int i = N - 1; i >= 1; --i)
{
while (lg >= 2 && det (stiva[lg-1], stiva[lg], p[i]) > 0)
--lg;
stiva[++lg] = p[i];
}
}
void citire ()
{
freopen ("infasuratoare.in", "r", stdin);
scanf ("%d", &N);
for (int i = 1; i <= N; ++i)
scanf ("%lf%lf", &p[i].x, &p[i].y);
}
void afisare ()
{
freopen ("infasuratoare.out", "w", stdout);
printf ("%d\n", lg - 1);
for (int i = lg; i >= 2; --i)
printf ("%.12lf %.12lf\n", stiva[i].x, stiva[i].y);
}
int main ()
{
citire ();
infasuratoare_convexa ();
afisare ();
return 0;
}