Pagini recente » Cod sursa (job #1882488) | Cod sursa (job #148539) | Cod sursa (job #379869) | Cod sursa (job #1835002) | Cod sursa (job #274814)
Cod sursa(job #274814)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 120010
typedef struct
{
double x, y;
} punct;
long n;
punct p[NMAX];
long hull[NMAX], h;
long ex[NMAX], h1;
void read()
{
long i;
double x, y;
scanf("%ld", &n);
for(i = 1; i <= n; ++i)
{
scanf("%lf %lf", &x, &y);
p[i].x = x;
p[i].y = y;
}
}
int cmp(const void *a, const void *b)
{
return ( (((punct *)a) -> x) - (((punct *)b) -> x) );
}
int cmp2(const void *a, const void *b)
{
return ( (((punct *)a) -> y) - (((punct *)b) -> y) );
}
double turn(punct a, punct b, punct c)
{
return ( (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y) );
}
void hull1()
{
long i;
h = 0;
hull[++h] = 1;
hull[++h] = 2;
for(i = 3; i <= n; ++i)
{
while(h > 1 && turn(p[ hull[h-1] ], p[ hull[h] ], p[i]) > 0)
--h;
hull[++h] = i;
}
}
void hull2()
{
long i;
h = 0;
hull[++h] = 1;
hull[++h] = 2;
for(i = 3; i <= n; ++i)
{
while(h > 1 && turn(p[ hull[h-1] ], p[ hull[h] ], p[i]) < 0)
--h;
hull[++h] = i;
}
}
int main()
{
long i, j;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
qsort(p+1, n, sizeof(punct), cmp);
//qsort(p+1, n, sizeof(punct), cmp2);
long last = 0;
for(i = 2; i <= n; ++i)
if(p[i].x != p[i-1].x)
{
qsort(p+last+1, i-last+1, sizeof(punct), cmp2);
last = i;
}
// for(i = 1; i <= n; ++i)
// printf("%lf %lf\n", p[i].x, p[i].y);
hull1();
//for(i = 1; i <= h; ++i)
// printf("%lf %lf\n", p[ hull[i] ].x, p[ hull[i] ].y);
memcpy(ex, hull, sizeof(hull));
h1 = h;
hull2();
printf("%ld\n", h1+h-2);
for(i = 1; i <= h; ++i)
printf("%lf %lf\n", p[ hull[i] ].x, p[ hull[i] ].y);
for(i = h1-1; i >= 2; --i)
printf("%lf %lf\n", p[ ex[i] ].x, p[ ex[i] ].y);
return 0;
}