Pagini recente » Cod sursa (job #1412185) | Cod sursa (job #2867562) | Cod sursa (job #602027) | Istoria paginii runda/imprumut_la_fmi/clasament | Cod sursa (job #1941861)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
const double kEps = 1e-12;
const double kInf = 1e10;
struct Point
{
double x, y;
bool operator==(const Point &a) const {
return (x == a.x) && (y == a.y);
}
};
Point LeftLower(const Point &a, const Point &b)
{
if (a.x - b.x < kEps) {
return a;
}
if (a.x - b.x > kEps) {
return b;
}
return (a.y - b.y < kEps) ? a : b;
}
bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
double res = a.x * (b.y - c.y) + a.y * (c.x - b.x) + b.x * c.y - b.y * c.x;
return (res > 0);
}
vector<Point> ConvexHull(vector<Point> &vec)
{
Point left = {kInf, kInf};
for (const auto &p : vec) {
left = LeftLower(left, p);
}
auto cmp = [left](const Point &a, const Point &b) -> bool {
if (a == left) {
return true;
}
if (b == left) {
return false;
}
return CounterClockwise(left, a, b);
};
sort(vec.begin(), vec.end(), cmp);
vector<Point> hull(2);
hull[0] = vec[0];
hull[1] = vec[1];
for (unsigned i = 2; i < vec.size(); ++i) {
while (hull.size() >= 2 &&
!CounterClockwise(hull[hull.size() - 2], hull.back(), vec[i])) {
hull.pop_back();
}
hull.push_back(vec[i]);
}
while (!CounterClockwise(hull[hull.size() - 2], hull.back(), hull[0])) {
hull.pop_back();
}
return hull;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<Point> points(n);
for (int i = 0; i < n; ++i) {
fin >> points[i].x >> points[i].y;
}
auto hull = ConvexHull(points);
fout << hull.size() << "\n";
for (const auto &p : hull) {
fout << fixed << setprecision(12) << p.x << " " << p.y << "\n";
}
return 0;
}