Pagini recente » Cod sursa (job #499779) | Cod sursa (job #2504261) | Cod sursa (job #134105) | Cod sursa (job #2522571) | Cod sursa (job #1087465)
#include <cstdio>
#include <algorithm>
#define Nmax 120005
using namespace std;
struct Punct
{
double x, y;
};
int N, Stiva[Nmax], vf = 2, Used[Nmax];
Punct P[Nmax];
bool Comp(Punct A, Punct B)
{
if (A.y == B.y)
return A.x < B.x;
return A.y < B.y;
}
void Citire()
{
scanf("%d", &N);
for (int i = 1; i <= N; ++i)
scanf("%lf%lf", &P[i].x, &P[i].y);
sort(P + 1, P + N + 1, Comp);
Stiva[1] = 1;
Stiva[2] = 2;
Used[1] = Used[2] = 1;
}
bool Determinant(Punct A, Punct B, Punct C)
{
if (A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - B.x * A.y - A.x * C.y > 0)
return true;
return false;
}
void Infasuratoare()
{
for (int i = 3; i <= N; ++i)
{
while (!Determinant(P[Stiva[vf - 1]], P[Stiva[vf]], P[i]) && vf > 1)
Used[Stiva[vf--]] = 0;
Stiva[++vf] = i;
Used[Stiva[vf]] = 1;
}
Used[1] = 0;
for(int i = N; i >= 1; --i)
if(!Used[i])
{
while (!Determinant(P[Stiva[vf - 1]], P[Stiva[vf]], P[i]) && vf > 1)
Used[Stiva[vf--]] = 0;
Stiva[++vf] = i;
Used[Stiva[vf]] = 1;
}
}
void Afisare()
{
vf--;
printf("%d\n", vf);
for (int i = 1; i <= vf; ++i)
printf("%.6lf %.6lf\n", P[Stiva[i]].x, P[Stiva[i]].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
Citire();
Infasuratoare();
Afisare();
return 0;
}