Pagini recente » Cod sursa (job #1460042) | Rating Popa Marilena (Marilena11) | Cod sursa (job #1853100) | Cod sursa (job #228263) | Cod sursa (job #812666)
Cod sursa(job #812666)
#include <cstdio>
#include <algorithm>
#include <cassert>
#define x first
#define y second
using namespace std;
typedef pair<double, double> Point;
const int MaxN = 125000;
const double Eps = 1e-12;
Point P[MaxN];
int N, Hull[MaxN], K;
bool Used[MaxN];
inline double Angle(Point P1, Point P2, Point P3) {
return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x;
}
void ConvexHull() {
sort(P+1, P+N+1);
for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
if (Used[i])
continue;
while (K > 1 && Angle(P[Hull[K-1]], P[Hull[K]], P[i]) <= Eps)
Used[Hull[K--]] = false;
Used[Hull[++K] = i] = true;
}
}
void Read() {
assert(freopen("infasuratoare.in", "r", stdin));
assert(scanf("%d", &N) == 1);
for (int i = 1; i <= N; ++i)
assert(scanf("%lf %lf", &P[i].x, &P[i].y) == 2);
}
void Print() {
assert(freopen("infasuratoare.out", "w", stdout));
printf("%d\n", K);
for (int i = 1; i <= K; ++i)
printf("%.7lf %.7lf\n", P[Hull[i]].x, P[Hull[i]].y);
}
int main() {
Read();
ConvexHull();
Print();
return 0;
}