Pagini recente » Cod sursa (job #2144556) | Rating Harip Alexandru (HaripAl3x) | Cod sursa (job #1552852) | Cod sursa (job #2990698) | Cod sursa (job #1073247)
#include <cstdio>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define sz size
#define add push_back
#define L S.sz()-1
#define erase pop_back
typedef double ld;
typedef pair <ld, ld> punct;
typedef vector <punct> poligon;
poligon P, S;
int n;
inline ld cross(punct A, punct B, punct C) {
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
inline bool cmp (punct A, punct B) {
return cross(P[0], A, B) < 0;
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d\n", &n);
int pos = 0;
for (int i = 0; i < n; ++i) {
punct p;
scanf ("%lf %lf", &p.x, &p.y);
P.add(p);
if (P[pos] > P[i])
pos = i;
}
swap (P[pos], P[0]);
poligon :: iterator it = P.begin();
it++;
sort(it, P.end(), cmp);
S.add (P[0]);
S.add (P[1]);
for (int i = 2; i < n; ++i) {
while (S.sz() > 1 && cross (S[L-1], S[L], P[i]) > 0) {
S.erase();
}
S.add (P[i]);
}
printf ("%d\n", S.sz());
for (int i = L; i >= 0; --i)
printf ("%.9lf %.9lf\n", S[i].x, S[i].y);
return 0;
}