Pagini recente » Profil agaman | Istoria paginii utilizator/stancupetre1988 | Istoria paginii utilizator/vasilel | Istoria paginii utilizator/life | Cod sursa (job #2006874)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define DIM 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz, k;
pair< double, double > v[DIM], st[DIM];
inline double det( pair< double, double > A, pair< double, double > B, pair< double, double > C ){
return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}
inline int cmp( const pair< double, double > &A, const pair< double, double > &B ){
return det( v[1], A, B ) < 0;
}
int main(){
fin >> n;
for( int i = 1; i <= n; i++ ){
fin >> v[i].x >> v[i].y;
}
//determin punctul cel mai din stanga dar sicel mai de jos ( determin primul pct din infasuratoare )
poz = 1;
for( int i = 2; i <= n; i++ ){
if( v[poz] > v[i] ){
poz = i;
}
}
//sortez dupa panta
swap( v[1], v[poz] );
sort( v + 2, v + n + 1, cmp );
//bag algoritmul de determinare a infasuratoarii convexe ( scanarea Graham )
k = 2;
st[1] = v[1];
st[2] = v[2];
for( int i = 3; i <= n; i++ ){
while( k >= 2 && det( st[k - 1], st[k], v[i] ) > 0 )
k--;
st[++k] = v[i];
}
fout << k << "\n";
for( int i = 1; i <= k; i++ ){
fout << setprecision(9) << fixed << st[i].x << " ";
fout << setprecision(9) << fixed << st[i].y << "\n";
}
return 0;
}