Pagini recente » ..::Hyper Kid Designer Profile::.. | Cod sursa (job #3309780) | ..::Hyper Kid Designer Profile::.. | Cod sursa (job #3358002) | Cod sursa (job #3357793)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <iomanip>
struct Point {
double x = 0, y = 0;
Point() = default;
Point(double x, double y) : x(x), y(y) {}
inline friend std::istream &operator>>(std::istream &is, Point &p) {
return is >> p.x >> p.y;
}
inline friend std::ostream &operator<<(std::ostream &os, const Point &p) {
return os << p.x << " " << p.y;
}
static double cross_product(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);
}
};
int main() {
std::ifstream input("infasuratoare.in");
std::ofstream output("infasuratoare.out");
int n;
input >> n;
std::vector<Point> points(n);
Point ref(INT_MAX, INT_MAX);
int pos = 0;
for (int i = 0; i < n; ++i) {
input >> points[i];
if (points[i].x < ref.x || (points[i].x == ref.x && points[i].y < ref.y)) {
ref = points[i];
pos = i;
}
}
std::swap(points[0], points[pos]);
auto cmp = [ref](const Point &a, const Point &b) {
double cp = Point::cross_product(ref, a, b);
if (cp == 0) {
double da = (a.x - ref.x) * (a.x - ref.x) + (a.y - ref.y) * (a.y - ref.y);
double db = (b.x - ref.x) * (b.x - ref.x) + (b.y - ref.y) * (b.y - ref.y);
return da < db;
}
return cp > 0;
};
std::sort(points.begin() + 1, points.end(), cmp);
std::vector<Point> hull;
hull.push_back(points[0]);
for (int i = 1; i < n; ++i) {
while (hull.size() >= 2) {
Point &a = hull[hull.size() - 2];
Point &b = hull[hull.size() - 1];
Point &c = points[i];
if (Point::cross_product(a, b, c) <= 0) {
hull.pop_back();
} else break;
}
hull.push_back(points[i]);
}
output << hull.size() << "\n";
output << std::setprecision(12) << std::fixed;
for (const auto &p : hull) {
output << p << "\n";
}
return 0;
}