Pagini recente » Cod sursa (job #2570117) | Cod sursa (job #613673) | Cod sursa (job #2845095) | Cod sursa (job #1529484) | Cod sursa (job #2156299)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ura {double x, y;};
ura v[120001], st[120001], sol[120001];
bool cmp (ura a, ura b) {
if (a.x < b.x)
return true;
else if (a.x > b.x)
return false;
else if (a.y < b.y)
return true;
else
return false;
}
double semnarie (ura p1, ura p2, ura p3) {
return p2.x * p1.y + p3.x * p2. y + p1.x * p3.y - p1.x * p2.y - p2.x * p3.y - p3.x * p1.y;
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int n, vf1, vf, i;
scanf ("%d", &n);
for (i = 1; i <= n; i++)
scanf ("%lf%lf", &v[i].x, &v[i].y);
sort (v + 1, v + n + 1, cmp);
vf = 0;
for (i = 1; i < n; i++) {
while (vf > 1 && semnarie (st[vf - 1], st[vf], v[i]) > 0)
vf--;
vf++;
st[vf] = v[i];
}
for (i = 1; i <= vf; i++)
sol[i] = st[i];
vf1 = vf;
vf = 0;
for (i = n; i > 1; i--) {
while (vf > 1 && semnarie (st[vf - 1], st[vf], v[i]) > 0)
vf--;
vf++;
st[vf] = v[i];
}
printf ("%d\n", vf1 + vf);
for (i = 1; i <= vf1; i++)
printf ("%lf %lf\n", sol[i].x, sol[i].y);
for (i = 1; i <= vf; i++)
printf ("%lf %lf\n", st[i].x, st[i].y);
return 0;
}