Pagini recente » Cod sursa (job #2828803) | Cod sursa (job #2937184) | Cod sursa (job #1552127) | Cod sursa (job #2256528) | Cod sursa (job #271723)
Cod sursa(job #271723)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 120010
#define EPS 1e-12
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)
{
if( ( (((punct *)a) -> x) == (((punct *)b) -> x) ) )
return ( (((punct *)a) -> y) - (((punct *)b) -> y) );
return ( (((punct *)a) -> x) - (((punct *)b) -> x) );
}
int f(double a, double b)
{
if(a + EPS < b) return -1;
if(b + EPS < a) return 1;
return 0;
}
double turn(punct a, punct b, punct c)
{
int res = f( (a.x-c.x)*(b.y-c.y), (b.x-c.x)*(a.y-c.y) );
return res;
}
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);
//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;
}