Pagini recente » Cod sursa (job #976884) | Cod sursa (job #1770285) | Cod sursa (job #171780) | Cod sursa (job #1211125) | Cod sursa (job #1165842)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int NMAX = 120010;
int N, K, HS;
pair<double, double> P[NMAX], Stack[NMAX], Hull[NMAX];
double Det(pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
return A.first * (B.second - C.second) + B.first * (C.second - A.second) + C.first * (A.second - B.second);
}
void Add()
{
K = 0;
Stack[K ++] = P[1];
Stack[K ++] = P[2];
for(int i = 3; i <= N; ++ i)
{
while(K >= 2 && Det(Stack[K - 2], Stack[K - 1], P[i]) < 0) K --;
Stack[K ++] = P[i];
}
for(int i = 0; i < K - 1; ++ i)
Hull[++ HS] = Stack[i];
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%i", &N);
for(int i = 1; i <= N; ++ i) scanf("%lf %lf", &P[i].first, &P[i].second);
sort(P + 1, P + N + 1); Add();
reverse(P + 1, P + N + 1); Add();
printf("%i\n", HS);
for(int i = 1; i <= HS; ++ i)
printf("%.6lf %.6lf\n", Hull[i].first, Hull[i].second);
}