Pagini recente » Cod sursa (job #239672) | Profil dnprx | Cod sursa (job #215948) | Borderou de evaluare (job #3325689) | Cod sursa (job #3301142)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
double x,y;
} punct;
punct puncte[120002];
double min_x, min_y;
int min_i;
double cross(punct p1, punct p2, punct p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
int compar(const void* a, const void* b) {
punct* p1 = (punct*)a;
punct* p2 = (punct*)b;
return cross(puncte[1], *p1, *p2) >= 0;
}
int main()
{
FILE* fin, *fout;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
int n,i;
fscanf(fin,"%d", &n);
fscanf(fin, "%ll %lf", &puncte[1].x, &puncte[1].y);
min_x = puncte[1].x, min_y = puncte[1].y, min_i = 1;
for(i=2;i<=n; i++){
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
if(puncte[i].x<min_x || puncte[i].x==min_x && puncte[i].y<min_y)
{
min_i = i;
min_x = puncte[i].x;
min_y = puncte[i].y;
}
}
punct aux;
aux = puncte[1];
puncte[1] = puncte[min_i];
puncte[min_i] = aux;
qsort(puncte+2, n-1, sizeof(punct), compar);
punct stv[120002];
stv[1] = puncte[1];
stv[2] = puncte[2];
int cap = 2;
for(i=3; i<=n; i++)
{
while(cross(stv[cap-1], stv[cap], puncte[i]) > 0 && cap>=2) cap--;
stv[++cap] = puncte[i];
}
fprintf(fout, "%d\n", cap);
for(i=cap; i>=1; i--)
fprintf(fout, "%lf %lf\n", stv[i].x, stv[i].y);
fclose(fin);
fclose(fout);
return 0;
}