Pagini recente » Cod sursa (job #1424035) | Cod sursa (job #769638) | Cod sursa (job #473194) | Cod sursa (job #2561801) | Cod sursa (job #708401)
Cod sursa(job #708401)
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 120000;
struct pct {double x; double y;} a[maxn], b[maxn], pi, aux;
long s[maxn], ind[maxn], ipi;
long i, N;
bool comp (long i, long j) {
return (double)(a[i].x - pi.x) * (a[j].y - pi.y) < (double)(a[j].x - pi.x) * (a[i].y - pi.y);
}
long double produs(pct x, pct y, pct z) {
return (long double)x.x * y.y + y.x * z.y + z.x * x.y - x.y * y.x - y.y * z.x - z.y * x.x;
}
void afisare();
void graham() {
sort(ind+1, ind+ind[0]+1, comp);
s[s[0] = 1] = ipi;
for (i = 1; i <= ind[0]; ++i) {
while (s[0] > 1 && produs(a[ s[s[0]-1] ], a[ s[s[0]] ], a[ ind[i] ]) > 0) {
--s[0];
}
s[++s[0]] = ind[i];
}
for (i = 0; i < s[0]; ++i) {
b[i] = a[s[i+1]];
}
for (i = 0; i < s[0]; ++i) {
a[i] = b[i];
}
N = s[0];
afisare();
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
pi.y = 1000000000;
scanf("%ld", &N);
ipi = 0;
for (i = 0; i < N; ++i) {
scanf("%lf %lf", &a[i].x, &a[i].y);
if (a[i].y < a[ipi].y || (a[i].y == a[ipi].y && a[i].x < a[ipi].x)) {
ipi = i;
}
}
pi = a[ipi];
for (i = 0; i < N; ++i) {
if (ipi != i) {
ind[++ind[0]] = i;
}
}
graham();
// for (i = 0; i < K; ++i) {
// scanf("%f %f\n", &a[++N].x, &a[N].y);
// if (a[i].y < pi.y || (a[i].y == pi.y && a[i].x < pi.x)) {
// pi = a[i];
// }
// graham();
// printf("%ld\n", N);
// }
return 0;
}
void afisare() {
printf("%ld\n", N);
printf("%lf %lf\n", a[0].x, a[0].y);
for (long i = N-1; i > 0; --i) {
printf("%lf %lf\n", a[i].x, a[i].y);
}
}