Pagini recente » Cod sursa (job #348038) | Cod sursa (job #1710313) | Cod sursa (job #936227) | Cod sursa (job #2772389) | Cod sursa (job #3359351)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
double x, y;
} Punct;
Punct pivot; /* punctul de referinta pentru sortarea unghiulara */
double cross(Punct O, Punct A, Punct B) {
return (A.x - O.x) * (B.y - O.y)
- (A.y - O.y) * (B.x - O.x);
}
double dist2(Punct a, Punct b) {
double dx = a.x - b.x, dy = a.y - b.y;
return dx*dx + dy*dy;
}
int cmp_unghi(const void* a, const void* b) {
Punct* p = (Punct*)a;
Punct* q = (Punct*)b;
double cr = cross(pivot, *p, *q);
if (cr > 1e-12) return -1; /* p e mai "la stanga" = vine primul in anti-orar */
if (cr < -1e-12) return 1;
/* coliniari: cel mai aproape de pivot vine primul */
double dp = dist2(pivot, *p);
double dq = dist2(pivot, *q);
if (dp < dq) return -1;
if (dp > dq) return 1;
return 0;
}
int main() {
FILE* fin = fopen("infasuratoare.in", "r");
FILE* fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
Punct* pts = (Punct*)malloc(n * sizeof(Punct));
for (int i = 0; i < n; i++)
fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
/* Gasim pivotul: y minim, la egalitate x minim */
int idx = 0;
for (int i = 1; i < n; i++) {
if (pts[i].y < pts[idx].y ||
(pts[i].y == pts[idx].y && pts[i].x < pts[idx].x))
idx = i;
}
/* Punem pivotul pe pozitia 0 */
Punct tmp = pts[0]; pts[0] = pts[idx]; pts[idx] = tmp;
pivot = pts[0];
/* Sortam restul punctelor dupa unghi polar fata de pivot */
qsort(pts + 1, n - 1, sizeof(Punct), cmp_unghi);
/* Graham Scan */
Punct* stiva = (Punct*)malloc(n * sizeof(Punct));
int top = 0;
stiva[top++] = pts[0];
stiva[top++] = pts[1];
for (int i = 2; i < n; i++) {
while (top >= 2 && cross(stiva[top-2], stiva[top-1], pts[i]) <= 0)
top--;
stiva[top++] = pts[i];
}
/* Stiva contine hull-ul in ordine trigonometrica, starting din pivot */
fprintf(fout, "%d\n", top);
for (int i = 0; i < top; i++)
fprintf(fout, "%.6f %.6f\n", stiva[i].x, stiva[i].y);
free(pts);
free(stiva);
fclose(fin);
fclose(fout);
return 0;
}