Pagini recente » Cod sursa (job #1771181) | Cod sursa (job #2175752) | Cod sursa (job #2467639) | Cod sursa (job #2046590) | Cod sursa (job #1497098)
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MULT = 2000000000;
const int XMAX = 1000000000;
const int NMAX = 120010;
const double Ep = 0.0000000000001;
struct punct {double x, y;};
punct v[NMAX];
int minim;
int N;
punct stiva[NMAX];
int h;
double determ (punct a, punct b, punct c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
bool criteriu (punct a, punct b) {
return determ (v[1], a, b) > 0;
}
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
fin >> N;
minim = 0;
v[0].x = v[0].y = MULT;
for (int i = 1; i <= N; i++) {
fin >> v[i].x >> v[i].y;
if (v[i].x < v[minim].x) {
minim = i;
}
else {
if (v[i].x == v[minim].x && v[i].y < v[minim].y) {
minim = i;
}
}
}
swap (v[minim], v[1]);
sort (v + 2, v + N + 1, criteriu);
stiva[1] = v[1];
h = 1;
for (int i = 2; i <= N; i++) {
while (h > 1 && determ (stiva[h - 1], stiva[h], v[i]) <= 0) {
h --;
}
stiva[++h] = v[i];
}
while (h > 1 && determ (stiva[h - 1], stiva[h], stiva[1]) <= 0) {
h --;
}
fout << h << '\n';
for (int i = 1; i <= h; i++) {
fout << fixed << setprecision (12) << stiva[i].x << " " << stiva[i].y << '\n';
}
return 0;
}