Pagini recente » Cod sursa (job #2805665) | Cod sursa (job #1868653) | Cod sursa (job #791224) | Cod sursa (job #2268750) | Cod sursa (job #934569)
Cod sursa(job #934569)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#define x first
#define y second
using namespace std;
typedef long long int64;
typedef vector<int>::iterator it;
typedef pair<double, double> Point;
const int oo = 0x3f3f3f3f;
const int MAX_N = 120005;
const double Eps = 1e-9;
vector<Point> Points, Hull;
inline double Det(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
vector<Point> ConvexHull(vector<Point>& points) {
int n = static_cast<int>(points.size());
vector<int> stack = vector<int>(n + 2, 0);
vector<bool> used = vector<bool>(n, false);
sort(points.begin(), points.end());
stack[++stack[0]] = 0;
for (int i = 1, p = 1; i >= 0; i += (p = (i == n - 1 ? -p : p))) {
if (used[i])
continue;
while (stack[0] > 1 && Det(points[stack[stack[0] - 1]], points[stack[stack[0]]], points[i]) < Eps)
used[stack[stack[0]--]] = false;
used[stack[++stack[0]] = i] = true;
}
vector<Point> hull;
for (int i = 1; i < stack[0]; ++i)
hull.push_back(points[stack[i]]);
return hull;
}
void Solve() {
}
void Read() {
ifstream in("infasuratoare.in");
int N; in >> N;
for (int i = 1; i <= N; ++i) {
Point newPoint; in >> newPoint.x >> newPoint.y;
Points.push_back(newPoint);
}
in.close();
}
void Print() {
ofstream out("infasuratoare.out");
out << Hull.size() << "\n";
for (size_t i = 0; i < Hull.size(); ++i)
out << fixed << setprecision(8) << Hull[i].x << " " << Hull[i].y << "\n";
out.close();
}
int main() {
Read();
Hull = ConvexHull(Points);
Print();
return 0;
}