Pagini recente » Cod sursa (job #485643) | Cod sursa (job #3234068) | Cod sursa (job #1875361) | Cod sursa (job #1433083) | Cod sursa (job #903098)
Cod sursa(job #903098)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef vector<int>::iterator it;
typedef pair<double, double> Point;
const int oo = 0x3f3f3f3f;
const int MAX_N = 120005;
const double Eps = 1e-12;
int N, Hull[MAX_N];
Point P[MAX_N];
bool Used[MAX_N];
inline double Det(Point P1, Point P2, Point P3) {
return (P2.x - P1.x) * (P3.y - P1.y) - (P3.x - P1.x) * (P2.y - P1.y);
}
void ConvexHull() {
sort(P + 1, P + N + 1);
Hull[++Hull[0]] = 1;
for (int i = 2, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
if (Used[i])
continue;
while (Hull[0] > 1 && Det(P[Hull[Hull[0] - 1]], P[Hull[Hull[0]]], P[i]) < Eps)
Used[Hull[Hull[0]--]] = false;
Used[Hull[++Hull[0]] = i] = true;
}
}
void Solve() {
ConvexHull();
}
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", Hull[0] - 1);
for (int i = 1; i < Hull[0]; ++i)
printf("%.8lf %.8lf\n", P[Hull[i]].x, P[Hull[i]].y);
}
int main() {
Read();
Solve();
Print();
return 0;
}