Pagini recente » Cod sursa (job #2773245) | Cod sursa (job #39704) | Cod sursa (job #1905505) | Cod sursa (job #2462830) | Cod sursa (job #2543439)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream inf("infasuratoare.in");
ofstream outf("infasuratoare.out");
struct Punct {
double x, y;
bool operator<(const Punct& other) const {
return x < other.x || (x == other.x && y < other.y);
}
};
const int NMAX = 120000;
Punct v[NMAX];
Punct hull[NMAX];
double det(Punct a, Punct b, Punct c) {
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + a.y * c.x - a.x * c.y;
}
int main() {
int n, hlen = 0;
inf >> n;
for(int i = 0; i < n; i++) {
inf >> v[i].x >> v[i].y;
}
sort(v, v + n);
for(int i = 0; i < n; i++) {
while(hlen > 1 && det(hull[hlen - 2], hull[hlen - 1], v[i]) < 0) {
hlen--;
}
hull[hlen++] = v[i];
}
for(int i = n - 2; i >= 0; i--) {
while(hlen > 1 && det(hull[hlen - 2], hull[hlen - 1], v[i]) < 0) {
hlen--;
}
hull[hlen++] = v[i];
}
hlen--;
outf << hlen << '\n';
outf << setprecision(6) << fixed;
for(int i = 0; i < hlen; i++) {
outf << hull[i].x << ' ' << hull[i].y << '\n';
}
return 0;
}