Pagini recente » Cod sursa (job #3292511) | Cod sursa (job #1948310) | Cod sursa (job #2523191) | Cod sursa (job #47917) | Cod sursa (job #3300581)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N 120005
#define EPS 1e-12
struct Point {
double x, y;
};
int n;
struct Point v[MAX_N];
int st[MAX_N];
int head;
int vis[MAX_N];
int cmp(const void *a, const void *b) {
struct Point *p = (struct Point *)a;
struct Point *q = (struct Point *)b;
if (fabs(p->x - q->x) > EPS) return (p->x < q->x) ? -1 : 1;
if (fabs(p->y - q->y) > EPS) return (p->y < q->y) ? -1 : 1;
return 0;
}
double cross_product(struct Point O, struct Point A, struct Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void read(FILE * fin) {
fscanf(fin,"%d", &n);
for (int i = 1; i <= n; ++i) {
fscanf(fin,"%lf %lf", &v[i].x, &v[i].y);
}
}
void convex_hull(FILE *fout) {
qsort(v + 1, n, sizeof(struct Point), cmp);
for (int i = 0; i <= n + 1; i++) vis[i] = 0;
st[1] = 1; st[2] = 2; head = 2;
vis[2] = 1;
for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) {
if (vis[i]) continue;
while (head >= 2 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < EPS) {
vis[st[head--]] = 0;
}
st[++head] = i;
vis[i] = 1;
}
int hull_size = head - 1;
fprintf(fout,"%d\n", hull_size);
for (int i = 1; i < head; ++i) {
fprintf(fout,"%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
}
}
int main() {FILE *fin,*fout;
fin= fopen("infasuratoare.in", "r");
fout= fopen("infasuratoare.out", "w");
read(fin);
convex_hull(fout);
return 0;
}