Pagini recente » Cod sursa (job #223592) | Statistici Damian Tudor (Augustinu04) | Cod sursa (job #1456784) | Cod sursa (job #1876987) | Cod sursa (job #2053953)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define EPS 1e-12
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int f[DIM], n, st[DIM], k;
struct Point{
double x, y;
} v[DIM];
inline double det( Point A, Point B, Point C ){
return ( A.x - C.x ) * ( B.y - C.y ) - ( B.x - C.x ) * ( A.y - C.y );
}
inline int 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 >> v[i].x >> v[i].y;
sort( v + 1, v + n + 1, cmp );
f[2] = 1;
st[1] = 1;
st[2] = 2;
k = 2;
//lower_bound
for( int i = 1; i <= n; i++ ){
if( f[i] == 1 )
continue;
while( k > 1 && det( v[ st[k - 1] ], v[ st[k] ], v[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( v[ st[k - 1] ], v[ st[k] ], v[i] ) < EPS ){
f[ st[k] ] = 0;
k--;
}
st[++k] = i;
f[i] = 1;
}
fout << k - 1 << "\n";
for( int i = 1; i < k; i++ ){
fout << setprecision(9) << fixed << v[ st[i] ].x << " ";
fout << setprecision(9) << fixed << v[ st[i] ].y << "\n";
}
return 0;
}