Pagini recente » Cod sursa (job #2269668) | Cod sursa (job #1465451) | Cod sursa (job #2470741) | Cod sursa (job #291414) | Cod sursa (job #3330426)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x, y;
bool operator < (const Point &other) const
{
if(x != other.x)
return (x < other.x);
return (y < other.y);
}
};
double cross_product(Point O, Point A, 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)
{
vector<Point> hull;
sort(points.begin(), points.end());
for(auto &P : points)
{
while(hull.size() >= 2 && cross_product(hull[hull.size() - 2], hull.back(), P) <= 0)
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_product(hull[hull.size() - 2], hull.back(), P) <= 0)
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;
}