Pagini recente » Cod sursa (job #884906) | Cod sursa (job #2617163) | Cod sursa (job #3814) | Cod sursa (job #1565271) | Cod sursa (job #271937)
Cod sursa(job #271937)
#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 swap(int i, int j)
{
punct aux;
aux = p[i];
p[i] = p[j];
p[j] = aux;
}
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)
{
if( ( (((punct *)a) -> x) == (((punct *)b) -> x) ) )
return ( (((punct *)a) -> y) - (((punct *)b) -> y) );
return ( (((punct *)a) -> x) - (((punct *)b) -> x) );
}
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 convexhull()
{
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);
convexhull();
memcpy(ex, hull, sizeof(hull));
h1 = h;
for(i = 1; i <= n/2; ++i)
swap(i, n-i+1);
convexhull();
printf("%ld\n", h1+h-2);
for(i = 1; i < h1; ++i)
printf("%lf %lf\n", p[ ex[i] ].x, p[ ex[i] ].y);
for(i = 1; i < h; ++i)
printf("%lf %lf\n", p[ n-hull[i]+1 ].x, p[ n-hull[i]+1 ].y);
return 0;
}