Pagini recente » Cod sursa (job #2491316) | Cod sursa (job #3165559) | Cod sursa (job #2869522) | Cod sursa (job #1345017) | Cod sursa (job #2376478)
#include<bits/stdc++.h>
using namespace std;
const int DIM = 120005;
const double EPS = 1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, st[DIM], f[DIM], K;
struct point{
double x, y;
} P[DIM];
double det( point S1, point S2, point P0 ){
return ( P0.x - S1.x ) * ( S2.y - S1.y ) - ( P0.y - S1.y ) * ( S2.x - S1.x );
}
inline bool cmp( const point &A, const point &B ){
if( ( A.x - B.x ) >= -EPS && ( A.x - B.x ) <= EPS )
return ( A.y - B.y ) < EPS;
return ( A.x - B.x ) < EPS;
}
int main(){
fin >> N;
for( int i = 1; i <= N; i++ )
fin >> P[i].x >> P[i].y;
sort( P + 1, P + N + 1, cmp );
f[2] = 1;
st[1] = 1; st[2] = 2;
K = 2;
///lower-bound
for( int i = 3; i <= N; i++ ){
while( K > 1 && det( P[ st[K - 1] ], P[ st[K] ], P[i] ) < EPS )
f[ st[K] ] = 0, K--;
st[++K] = i;
f[i] = 1;
}
///upper-bound
for( int i = N; i >= 1; i-- ){
if( f[i] == 1 )
continue;
while( K > 1 && det( P[ st[K - 1] ], P[ st[K] ], P[i] ) < EPS )
f[ st[K] ] = 0, K--;
st[++K] = i;
f[i] = 1;
}
K--; ///pct cel mai din stanga apare de 2 ori
fout << K << "\n";
for( int i = 1; i <= K; i++ ){
fout << setprecision(9) << fixed << P[ st[i] ].x << " ";
fout << setprecision(9) << fixed << P[ st[i] ].y << "\n";
}
return 0;
}