Pagini recente » Cod sursa (job #166384) | Cod sursa (job #638347) | Cod sursa (job #2056088) | Cod sursa (job #1809865) | Cod sursa (job #702744)
Cod sursa(job #702744)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 120001
#define x first
#define y second
#define PDD pair< double, double >
int N, i, sens, Lg;
int Stiva[NMAX];
bool Used[NMAX];
PDD P[NMAX];
inline bool Semn( PDD A, PDD B, PDD C )
{
double ecA = A.y - B.y, ecB = B.x - A.x, ecC = A.x*B.y - A.y*B.x;
return ( ecA*C.x + ecB*C.y + ecC < 0 );
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N );
for( i = 1; i <= N; ++i )
scanf("%lf%lf", &P[i].x, &P[i].y );
sort( P + 1, P + N+1 );
memset( Used, false, sizeof(Used) );
Stiva[1] = 1, Stiva[2] = 2, Used[2] = true;
Lg = 2, i = 3, sens = 1;
while( !Used[1] )
{
while( Used[i] )
{
if( i == N ) sens = -1;
i += sens;
}
while( Lg > 1 && Semn( P[ Stiva[Lg-1] ], P[ Stiva[Lg] ], P[i] ) )
Used[ Stiva[Lg--] ] = false;
Used[i] = true, Stiva[++Lg] = i;
}
printf("%d\n", Lg - 1 );
for( i = 1; i < Lg; ++i )
printf("%.6lf %.6lf\n", P[ Stiva[i] ].x, P[ Stiva[i] ].y );
return 0;
}