Pagini recente » Cod sursa (job #19958) | Cod sursa (job #861244) | Cod sursa (job #2402713) | Cod sursa (job #396247) | Cod sursa (job #1165590)
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
vector <pair <double, double> > P, stiva;
int n, poz;
double cross(pair <double, double> A, pair <double, double> B, pair <double, double> C) {
return (B.first - A.first) * (C.second - A.second) - (C.first - A.first) * (B.second - A.second);
}
bool cmp(pair <double, double> A, pair <double, double> B) {
return cross (P[0], A, B) < 0;
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d", &n);
for (int i = 0; i < n; ++i) {
double x, y;
scanf ("%lf %lf", &x, &y);
P.push_back (make_pair (x, y));
if (P[i] < P[poz])
poz = i;
}
swap (P[0], P[poz]);
sort ((P.begin() + 1), P.end(), cmp);
stiva.push_back (P[0]);
stiva.push_back (P[1]);
for (int i = 2; i < n; ++i) {
while (stiva.size() > 1 && cross (stiva[stiva.size() - 2], stiva[stiva.size() - 1], P[i]) > 0)
stiva.pop_back();
stiva.push_back (P[i]);
}
printf ("%d\n", stiva.size());
for (vector <pair <double, double> > :: reverse_iterator it = stiva.rbegin(); it != stiva.rend(); ++it)
printf ("%.9lf %.9lf\n", it->first, it->second);
}