Pagini recente » Cod sursa (job #715122) | Cod sursa (job #756199) | Cod sursa (job #472235) | Cod sursa (job #3222549) | Cod sursa (job #274757)
Cod sursa(job #274757)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#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(punct a, punct b)
{
if(a.x < b.x)
return 1;
if(a.x == b.x && a.y < b.y)
return 1;
return 0;
}
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);
sort(p+1, p+n+1, cmp);
// 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;
}