Pagini recente » Cod sursa (job #1603640) | Cod sursa (job #278472) | Cod sursa (job #2277967) | Cod sursa (job #420984) | Cod sursa (job #3330418)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120001;
const long double EPS = 1e-12;
struct Point
{
long double x, y;
bool operator < (const Point &other) const
{
if(x != other.x)
return (x < other.x);
return (y < other.y);
}
};
long double cross(const Point &O, const Point &A, const Point &B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<Point> convex_hull(vector<Point> &points)
{
sort(points.begin(), points.end());
vector<Point> hull;
for(auto &P : points)
{
while(hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), P) <= EPS)
hull.pop_back();
hull.push_back(P);
}
int lower_size = hull.size();
reverse(points.begin(), points.end());
for(auto &P : points)
{
while(hull.size() > lower_size && cross(hull[hull.size() - 2], hull.back(), P) <= EPS)
hull.pop_back();
hull.push_back(P);
}
hull.pop_back();
return hull;
}
int main()
{
int n;
fin >> n;
vector<Point> points(n);
for(int i = 0; i < n; i++)
fin >> points[i].x >> points[i].y;
vector<Point> hull = convex_hull(points);
fout << hull.size() << "\n";
for(auto &P : hull)
fout << fixed << setprecision(12) << P.x << " " << P.y << "\n";
fin.close();
fout.close();
return 0;
}