Pagini recente » Cod sursa (job #1017820) | Cod sursa (job #748389) | Cod sursa (job #1020642) | Cod sursa (job #544894) | Cod sursa (job #3309205)
/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
using d64 = long double;
const d64 EPS = 1e-12;
struct Point {
d64 x, y;
};
d64 cp(Point A, Point B, Point C) {
return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}
int N;
vector<Point> P;
int main()
{
fin >> N;
P.resize(N);
for(int i = 0; i < N; i++) {
fin >> P[i].x >> P[i].y;
}
sort(P.begin(), P.end(), [](Point &a, Point &b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
vector<Point> upper_hull;
upper_hull.push_back(P[0]);
upper_hull.push_back(P[1]);
for(int i = 2; i < N; i++) {
while(upper_hull.size() >= 2 && cp(upper_hull[upper_hull.size() - 2], upper_hull[upper_hull.size() - 1], P[i]) < EPS) {
upper_hull.pop_back();
}
upper_hull.push_back(P[i]);
}
vector<Point> lower_hull;
lower_hull.push_back(P[N - 1]);
lower_hull.push_back(P[N - 2]);
for(int i = N - 3; i >= 0; i--) {
while(lower_hull.size() >= 2 && cp(lower_hull[lower_hull.size() - 2], lower_hull[lower_hull.size() - 1], P[i]) < EPS) {
lower_hull.pop_back();
}
lower_hull.push_back(P[i]);
}
reverse(lower_hull.begin(), lower_hull.end());
reverse(upper_hull.begin(), upper_hull.end());
lower_hull.pop_back();
upper_hull.pop_back();
vector<Point> hull = lower_hull;
hull.insert(hull.end(), upper_hull.begin(), upper_hull.end());
fout << hull.size() << "\n";
fout << fixed;
for(int i = 0; i < hull.size(); i++) {
fout << setprecision(12) << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}