Pagini recente » Cod sursa (job #1815830) | Cod sursa (job #2261767) | Cod sursa (job #3128533) | Cod sursa (job #338128) | Cod sursa (job #1379975)
#include <cstdio>
#include <stack>
#include <algorithm>
#define NMAX 120005
using namespace std;
pair <double, double> P[NMAX], stiva[NMAX];
int N, vf = 2;
void citire()
{
scanf("%d", &N);
for (int i = 1; i <= N; ++i)
scanf("%lf %lf", &P[i].first, &P[i].second);
}
inline double determinant(pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}
inline int cmp(const pair <double, double>& A, const pair <double, double>& B)
{
return determinant(P[1], A, B) < 0;
}
void infasuratoare()
{
sort(P + 1, P + N + 1);
sort(P + 2, P + N + 1, cmp);
stiva[1] = P[1];
stiva[2] = P[2];
for (int i = 3; i <= N; ++i)
{
while (vf >= 2 && determinant(stiva[vf - 1], stiva[vf], P[i]) > 0)
vf--;
stiva[++vf] = P[i];
}
}
void afisare()
{
printf("%d\n", vf);
for (int i = vf; i >= 1; --i)
printf("%.9lf %.9lf\n", stiva[i].first, stiva[i].second);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
infasuratoare();
afisare();
return 0;
}