Pagini recente » Cod sursa (job #893770) | Cod sursa (job #2791516) | Cod sursa (job #325118) | Cod sursa (job #2111804) | Cod sursa (job #2542518)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream inf("infasuratoare.in");
ofstream outf("infasuratoare.out");
const int NMAX = 120000;
struct Point {
double x, y;
};
Point v[NMAX];
int infas[NMAX];
bool viz[NMAX];
double cross_product(Point o, Point a, Point b) { /// AOB <= 180deg, in sens trigonometric de la A la B
return ((a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x));
}
int main() {
int n;
inf >> n;
for(int i = 0; i < n; i++) {
inf >> v[i].x >> v[i].y;
}
sort(v, v + n, [](Point a, Point b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
int infaslen = 2;
infas[0] = 0;
infas[1] = 1;
viz[1] = true;
for(int i = 0; i < n; i++) {
while(infaslen > 1 && cross_product(v[infas[infaslen - 2]], v[infas[infaslen - 1]], v[i]) <= 0) {
viz[infas[--infaslen]] = false;
}
viz[i] = true;
infas[infaslen++] = i;
}
int x = infaslen;
for(int i = n - 1; i; i--) {
if(viz[i]) {
continue;
}
while(infaslen > 1 && cross_product(v[infas[infaslen - 2]], v[infas[infaslen - 1]], v[i]) <= 0) {
viz[infas[--infaslen]] = false;
}
viz[i] = true;
infas[infaslen++] = i;
}
outf << infaslen << '\n';
outf << setprecision(6) << fixed;
for(int i = 0; i < infaslen; i++) {
outf << v[infas[i]].x << ' ' << v[infas[i]].y << '\n';
}
return 0;
}