Pagini recente » Cod sursa (job #1666215) | Cod sursa (job #2512548) | Cod sursa (job #1666212) | Cod sursa (job #1529290) | Cod sursa (job #3340442)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
};
double cross(Point A, Point B, Point C) {
return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}
double dist(Point A, Point B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y)* (A.y - B.y));
}
bool cmp(Point a, Point b, Point p0) {
double cr = cross(p0, a, b);
if(fabs(cr) < 1e-12)
return dist(a, p0) < dist(b, p0);
return cr > 0;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N; fin >> N;
vector<Point> pts(N);
for(int i = 0; i < N; i++)
fin >> pts[i].x >> pts[i].y;
Point p0 = pts[0];
for(auto &p: pts)
if(p.y < p0.y || (p.y == p0.y && p.x < p0.x))
p0 = p;
sort(pts.begin(), pts.end(), [&](Point a, Point b){
return cmp(a,b,p0);
});
vector<Point> hull;
for(auto p: pts) {
while(hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), p) <= 0)
hull.pop_back();
hull.push_back(p);
}
fout << hull.size() << "\n";
for(auto p: hull)
fout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
return 0;
}