Pagini recente » Cod sursa (job #1092146) | Cod sursa (job #1376827) | Cod sursa (job #2142158) | Cod sursa (job #334893) | Cod sursa (job #1106772)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
typedef pair<double, double> Point;
const int MAX_N = 120100;
int N;
Point p[MAX_N];
int hull[MAX_N];
bool used[MAX_N];
int head;
void convex_hull();
double cross_product(int o, int a, int b);
int main() {
fin >> N;
for (int i = 1; i <= N; i += 1) {
fin >> p[i].x >> p[i].y;
}
sort(p + 1, p + N + 1);
convex_hull();
fout << head << '\n';
for (int i = 1; i <= head; i += 1) {
fout << p[hull[i]].x << ' ' << p[hull[i]].y << '\n';
}
}
void convex_hull() {
head = 0;
hull[++head] = 1;
hull[++head] = 2;
used[2] = true;
for (int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
if (used[i]) continue;
while (head >= 2 && cross_product(hull[head - 1], hull[head], i) > 0) {
used[hull[head]] = false;
head -= 1;
}
used[i] = true;
hull[++head] = i;
}
head -= 1;
}
inline double cross_product(int o, int a, int b) {
return (p[a].x - p[o].x) * (p[b].y - p[o].y) -
(p[a].y - p[o].y) * (p[b].x - p[o].x);
}