Pagini recente » Cod sursa (job #704272) | Cod sursa (job #1947923)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
const double kInf = 1e12;
const double kEps = 1e-12;
struct Point { double x, y; };
inline double Abs(double a) { return a < 0 ? -a : a; }
inline bool Smaller(double a, double b) { return a - b < kEps; }
inline bool Equal(double a, double b) { return Abs(a - b) < kEps; }
bool operator==(const Point &a, const Point &b)
{
return Equal(a.x, b.x) && Equal(a.y, b.y);
}
inline bool CounterClock(const Point &a, const Point &b, const Point &c)
{
double delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return delta > 0;
}
vector<Point> FindHull(vector<Point> &vec)
{
Point left = {kInf, kInf};
for (const auto &p : vec) {
if (Smaller(p.x, left.x) ||
(Equal(p.x, left.x) && Smaller(p.y, left.y))) {
left = p;
}
}
auto cmp = [left](const Point &a, const Point &b) -> bool {
if (a == left){
return true;
} else if (b == left) {
return false;
}
return CounterClock(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 &&
!CounterClock(hull[hull.size() - 2], hull.back(), vec[i])) {
hull.pop_back();
}
hull.push_back(vec[i]);
}
return hull;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<Point> vec(n);
for (int i = 0; i < n; ++i) {
fin >> vec[i].x >> vec[i].y;
}
auto hull = FindHull(vec);
fout << hull.size() << "\n";
for (const auto &p : hull) {
fout << fixed << setprecision(12) << p.x << " " << p.y << "\n";
}
return 0;
}