Pagini recente » Cod sursa (job #1342028) | Cod sursa (job #1236231) | Cod sursa (job #2978574) | Cod sursa (job #233654) | Cod sursa (job #2680967)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f ( "infasuratoare.in" );
ofstream g ( "infasuratoare.out" );
struct Punct
{
int x, y;
};
Punct P[100002], St[1002];
int N, H;
void afis()
{
g << H << '\n';
for ( int i = 1; i <= H; i++ )
g << St[i].x << ' ' << St[i].y << '\n';
}
void swap ( Punct &A, Punct &B )
{
Punct aux;
aux = A;
A = B;
B = aux;
}
inline long long patrat ( long long x )
{
return x * x;
}
long long distp ( const Punct &A, const Punct &B )
{
return patrat ( A.x - B.x ) + patrat ( A.y - B.y );
}
int compy ( const Punct &A, const Punct &B )
{
if ( A.y == B.y ) return A.x < B.x;
return A.y < B.y;
}
long long det ( const Punct &A, const Punct &B, const Punct &C )
{
return ( long long ) ( A.x - B.x ) ( B.y - C.y ) - ( long long ) ( A.y - B.y ) ( B.x - C.x );
}
int compd ( const Punct &A, const Punct &B )
{
long long dd = det ( P[1], A, B );
if ( dd == 0 )
return distp ( P[1], A ) < distp ( P[1], B );
return dd > 0;
}
int main()
{
f >> N;
int pmin = 1;
for ( int i = 1; i <= N; i++ )
{
f >> P[i].x >> P[i].y;
if ( compy ( P[i], P[pmin] ) )
pmin = i;
}
swap ( P[pmin], P[1] );
sort ( P + 2, P + N + 1, compd );
St[1] = P[1];
St[2] = P[2];
H = 2;
P[N + 1] = P[1];
for ( int i = 3; i <= N + 1; i++ )
{
while ( H >= 2 && det ( St[H - 1], St[H], P[i] ) <= 0 )
H--;
St[++H] = P[i];
}
H--;
afis();
return 0;
}