Pagini recente » Cod sursa (job #300840) | Cod sursa (job #733592) | Utilizatori inregistrati la preONI 2008, Runda 3, Clasa a 10-a | Cod sursa (job #883830) | Cod sursa (job #899194)
Cod sursa(job #899194)
#include <cstdio>
#include <algorithm>
#define NMAX 120005
#define PDD pair< double, double >
#define x first
#define y second
using namespace std;
int N, i, sens, Lg;
PDD P[NMAX];
bool Used[NMAX];
int Stack[NMAX];
inline double Semn( PDD A, PDD B, PDD C )
{
return A.x*B.y + B.x*C.y + C.x*A.y - B.y*C.x - C.y*A.x - A.y*B.x;
}
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 );
Stack[1] = 1;
Stack[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[Stack[Lg - 1]], P[Stack[Lg]], P[i] ) < 0 )
Used[ Stack[Lg--] ] = false;
Stack[++Lg] = i;
Used[i] = true;
}
Lg--;
printf("%d\n", Lg);
for( i = 2; i <= Lg + 1; ++i )
printf("%.6lf %.6lf\n", P[Stack[i]].x, P[Stack[i]].y);
return 0;
}