Pagini recente » Cod sursa (job #671958) | Cod sursa (job #3337647) | Monitorul de evaluare | Cod sursa (job #1386154) | Cod sursa (job #3309203)
/******************************************************************************
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> hull;
hull.push_back(P[0]);
hull.push_back(P[1]);
for(int i = 2; i < N; i++) {
while(hull.size() >= 2 && cp(hull[hull.size() - 2], hull[hull.size() - 1], P[i]) <= EPS) {
hull.pop_back();
}
hull.push_back(P[i]);
}
for(int i = N - 2; i >= 0; i--) {
while(hull.size() >= 2 && cp(hull[hull.size() - 2], hull[hull.size() - 1], P[i]) <= EPS) {
hull.pop_back();
}
hull.push_back(P[i]);
}
hull.pop_back();
reverse(hull.begin(), hull.end());
fout << hull.size() << "\n";
for(int i = 0; i < hull.size(); i++) {
fout << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}