Pagini recente » Cod sursa (job #1375594) | Cod sursa (job #2288225) | Cod sursa (job #2737917) | Cod sursa (job #542315) | Cod sursa (job #657792)
Cod sursa(job #657792)
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 120002;
const double INF = 1000000000;
int n, nn = 2, poz;
struct punct {
double x, y, p;
};
punct a[N], s[N], z;
void citire() {
z.x = z.y = INF;
scanf("%d ", &n);
for (int i = 0; i < n; ++i) {
scanf("%lf %lf ", &a[i].x, &a[i].y);
if (a[i].x < z.x || (a[i].x == z.x && a[i].y < z.y)) {
z.x = a[i].x;
z.y = a[i].y;
poz = i;
}
}
a[poz] = a[n - 1];
--n;
}
void panta() {
for (int i = 0; i < n; ++i)
if (a[i].x == z.x)
a[i].p = INF;
else
a[i].p = (a[i].y - z.y) / (a[i].x - z.x);
}
bool comp(punct a, punct b) {
if (a.p > b.p)
return false;
return true;
}
bool determinant(punct a, punct b, punct c) {
double det = (double) a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
if (det >= 0)
return 1;
return 0;
}
void infasuratoare() {
s[0] = z;
s[1] = a[0];
for (int i = 1; i < n; ++i)
if (determinant(s[nn - 2], s[nn - 1], a[i]) == 1)
s[nn++] = a[i];
else {
while (determinant(s[nn - 2], s[nn - 1], a[1]) == 0)
s[--nn] = a[i];
++nn;
}
}
void afisare() {
printf("%d\n", nn);
for (int i = 0; i < nn; ++i)
printf("%lf %lf\n", s[i].x, s[i].y);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
panta();
sort(a, a + n, comp);
infasuratoare();
afisare();
return 0;
}