Pagini recente » Cod sursa (job #2087536) | Cod sursa (job #1652856) | Cod sursa (job #615480) | Cod sursa (job #2133953) | Cod sursa (job #2073675)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120000;
const int INF = 2e9;
struct coord{double x; double y;};
coord v[MAXN + 1], st[MAXN + 1];
double S(coord a, coord b, coord c) {
double A = 0;
A = a.x * b.y - b.x * a.y + b.x * c.y - c.x * b.y + c.x * a.y - a.x * c.y;
return A;
}
bool cmp(coord a, coord b) {
if (S(v[1], a, b) >= 0)
return true;
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(200);
double minx, miny;
coord aux;
int n, i, poz, vf;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
minx = miny = INF;
for (i = 1; i <= n; i++) {
f >> v[i].x >> v[i].y;
if (v[i].y < miny || (v[i].y == miny && v[i].x < minx)) {
miny = v[i].y;
minx = v[i].x;
poz = i;
}
}
aux = v[1];
v[1] = v[poz];
v[poz] = aux;
sort(v + 2, v + n + 1, cmp);
st[1] = v[1];
st[2] = v[2];
vf = 2;
v[n + 1] = v[1];
for (i = 3; i <= n + 1;i++) {
while (vf >= 2 && S(st[vf -1 ], st[vf], v[i]) < 0)
vf--;
st[++vf]=v[i];
}
g << vf - 1 << '\n';
for (i = 1; i < vf; i++) {
g << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}