Pagini recente » Cod sursa (job #271988) | Cod sursa (job #273266)
Cod sursa(job #273266)
#include <stdio.h>
#include <math.h>
#define NMAX 120002
#define eps 0.000000000001
int N, st[NMAX];
struct POINT
{
double x, y;
};
POINT a[NMAX];
double FABS( double x)
{
return x < 0.0 ? -x : x;
}
double dist(POINT A, POINT B)
{
return sqrt( ( A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) );
}
int same_point(POINT A, POINT B)
{
return ( FABS( A.x - B.x) < eps && FABS(A.y - B.y) < eps );
}
int ccw(POINT A, POINT B, POINT C)
{
double p;
p = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * ( C.x - B.x);
if ( FABS(p) < eps )
return 0;
if ( p > eps)
return 1;
return -1;
}
int comp(POINT A, POINT B, POINT C)
{
int c;
c = ccw(A, B, C);
if ( c == 1)
return 1;
else
if ( c == - 1)
return 0;
else
{
if ( dist(A, C) - dist(A, B) >= eps)
return 1;
else
return 0;
}
}
int partitie(int st, int dr)
{
int i, j;
POINT aux, pivot;
i = st - 1;
j = dr + 1;
pivot = a[(st + dr) / 2];
while (1)
{
do { ++i; } while ( comp(a[0], a[i], pivot) == 1 && !same_point(a[i], pivot) );
do { --j; } while ( comp(a[0], a[j], pivot) == 0 && !same_point(a[j], pivot) );
if ( i < j)
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
else
return j;
}
}
void sort(int st, int dr)
{
int m;
if ( st < dr)
{
m = partitie(st, dr);
sort( st, m);
sort( m + 1, dr);
}
}
void solve()
{
int top, i;
top = 1;
i = 2;
st[0] = 0;
st[1] = 1;
a[N] = a[0];
while ( i <= N)
{
if ( ccw( a[st[top - 1]], a[st[top]], a[i]) == 1)
{
st[++top] = i;
i++;
}
else
top--;
}
printf("%d\n", top);
for ( i = 0; i < top; i++)
printf("%lf %lf\n", a[st[i]].x, a[st[i]].y);
}
int main()
{
int i, poz;
POINT min, aux;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for ( i = 0; i < N; i++)
scanf("%lf %lf", &a[i].x, &a[i].y);
min = a[0];
poz = 0;
for ( i = 1; i < N; i++)
if ( a[i].y < min.y || ( FABS(a[i].y - min.y) < eps && a[i].x < min.x) )
{
min = a[i];
poz = i;
}
aux = a[0];
a[0] = a[poz];
a[poz] = aux;
sort(1, N - 1);
solve();
return 0;
}