Pagini recente » Cod sursa (job #2990732) | Cod sursa (job #2753052) | Cod sursa (job #1351891) | Istoria paginii utilizator/kitchen367 | Cod sursa (job #2256263)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
#include <cstring>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "infasuratoare";
#define USE_FILES
#ifdef USE_FILES
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define cin fin
#define cout fout
#endif
struct Point {
double x, y;
};
double doubleSignedTriangleArea(const Point& p1, const Point& p2, const Point& p3) {
return (p1.x - p3.x) * (p2.y - p3.y) - (p1.y - p3.y) * (p2.x - p3.x);
}
bool ccw(const Point& p1, const Point& p2, const Point& p3) {
return doubleSignedTriangleArea(p1, p2, p3) > 0;
}
std::vector<Point> computeConvexHull(std::vector<Point>& points) {
auto compareByX = [](const auto& p1, const auto& p2) {
if (p1.x == p2.x) {
// can't happen?
return (p1.y < p2.y);
}
return p1.x < p2.x;
};
Point& bottomLeft = *std::min_element(
points.begin(),
points.end(),
compareByX
);
// place minimum in the first position
std::swap(*points.begin(), bottomLeft);
auto compareByAngle = [bottomLeft] (const auto& p1, const auto& p2) {
return ccw(bottomLeft, p1, p2);
};
std::sort(
points.begin() + 1,
points.end(),
compareByAngle
);
std::vector<Point> ch;
auto breaksCcwProperty = [&ch](const Point& point) {
const Point& beforeLast = ch[ch.size() - 2];
const Point& last = ch[ch.size() - 1];
return ch.size() >= 2 && !ccw(beforeLast, last, point);
};
// since bottomLeft is the first element of the `points` array, it will be inserted first
for (const auto& point : points) {
while (breaksCcwProperty(point)) {
ch.pop_back();
}
ch.push_back(point);
}
return ch;
}
int main() {
int n;
std::cin >> n;
std::vector<Point> points(n);
for (auto& p : points) {
std::cin >> p.x >> p.y;
}
auto ch = computeConvexHull(points);
std::cout << ch.size() << '\n';
for (const auto& p : ch) {
std::cout << p.x << ' ' << p.y << '\n';
}
return 0;
}