Pagini recente » Cod sursa (job #3331193) | Cod sursa (job #1322762) | Cod sursa (job #1322771) | Cod sursa (job #2683880) | Cod sursa (job #3359144)
#include <stdio.h>
#include <stdlib.h>
#define EPS 1e-9
typedef struct {
double x, y;
} punct;
int compara(const void *a, const void *b) {
punct *p1=(punct*)a;
punct *p2=(punct*)b;
if (p1->x!=p2->x) {
return (p1->x>p2->x)-(p1->x<p2->x);
}
return (p1->y>p2->y)-(p1->y<p2->y);
}
double produs_vect(punct A, punct B, punct C) {
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
punct puncte[120005];
punct inf_conv[240010];
int main() {
FILE *f=fopen("infasuratoare.in", "r");
FILE *g=fopen("infasuratoare.out", "w");
if (f==NULL || g==NULL)
{
return 0;
}
int n;
if (fscanf(f, "%d", &n)!=1)
{
fclose(f);
fclose(g);
return 0;
}
for (int i=0; i<n; i++) {
fscanf(f, "%lf %lf", &puncte[i].x, &puncte[i].y);
}
qsort(puncte, n, sizeof(punct), compara);
int H=0;
for (int i=0; i<n; i++) {
while (H>=2 && produs_vect(inf_conv[H-2], inf_conv[H-1], puncte[i])<=EPS) {
H--;
}
inf_conv[H++]=puncte[i];
}
int limita_jos=H;
for (int i=n-2; i>=0; i--) {
while (H>limita_jos && produs_vect(inf_conv[H-2], inf_conv[H-1], puncte[i])<=EPS) {
H--;
}
inf_conv[H++]=puncte[i];
}
if (n>1) {
H--;
}
fprintf(g, "%d\n", H);
for (int i=0; i<H; i++) {
fprintf(g, "%.6lf %.6lf\n", inf_conv[i].x, inf_conv[i].y);
}
fclose(f);
fclose(g);
return 0;
}