Pagini recente » Cod sursa (job #1695286) | Monitorul de evaluare | Cod sursa (job #1011004) | Cod sursa (job #187624) | Cod sursa (job #3301135)
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
typedef struct { ll x, y; } P;
int cmpP(const void *a, const void *b) {
P *p = (P*)a, *q = (P*)b;
if (p->x < q->x) return -1;
if (p->x > q->x) return 1;
if (p->y < q->y) return -1;
if (p->y > q->y) return 1;
return 0;
}
ll cross(P a, P b, P c) {
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
int main() {
int n;
if (scanf("%d", &n) != 1) return 0;
P *a = malloc(n * sizeof(P));
for (int i = 0; i < n; ++i) scanf("%lld %lld", &a[i].x, &a[i].y);
qsort(a, n, sizeof(P), cmpP);
P *hull = malloc(2 * n * sizeof(P));
int m = 0;
for (int i = 0; i < n; ++i) {
while (m >= 2 && cross(hull[m-2], hull[m-1], a[i]) <= 0) m--;
hull[m++] = a[i];
}
int t = m;
for (int i = n-2; i >= 0; --i) {
while (m > t && cross(hull[m-2], hull[m-1], a[i]) <= 0) m--;
hull[m++] = a[i];
}
if (n > 1) m--;
printf("%d\n", m);
for (int i = 0; i < m; ++i)
printf("%lld %lld\n", hull[i].x, hull[i].y);
return 0;
}