Pagini recente » Cod sursa (job #2284885) | Cod sursa (job #1373337) | Cod sursa (job #2180109) | Cod sursa (job #345062) | Cod sursa (job #1247789)
#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000;
const double EPS = 1.e-12;
struct PCT{
double x,y;
};
/// Const pt infasuratoare
PCT XX;
/// Restul
vector <PCT> v, r;
int N;
bool Alege_XX( PCT A ) {
return ( A.x < XX.x || ( fabs(A.x-XX.x)<EPS && A.y < XX.y ) );
}
double CCW( PCT A, PCT B, PCT C ) {
double val= (B.x-A.x)*(C.y-B.y) - (B.y-A.y)*(C.x-B.x);
if( val >= EPS ) return 1;
if( val <= -EPS ) return -1;
return 0;
}
bool cmp_panta( PCT A, PCT B ) {
return ( CCW( XX, A, B ) > 0.0 );
}
void Infas_Convexa( vector<PCT> &v, vector<PCT> &r ) {
r.clear();
PCT st[NMAX+2]; int st_ind= 0;
sort( v.begin(), v.end(), cmp_panta );
st[ ++st_ind ]= v[0]; r.push_back( v[0] );
st[ ++st_ind ]= v[1]; r.push_back( v[1] );
for( int i= 2; i<(int)v.size(); ++i ) {
if( CCW( st[ st_ind-1 ], st[ st_ind ], v[i] ) > 0.0 ) {
st[ ++st_ind ]= v[i]; /// Pun in stiva
r.push_back( v[i] );
}
else {
--st_ind; /// Scot
st[ ++st_ind ]= v[i]; /// Pun elementul curent
r[ st_ind - 1 ]= v[i];
}
}
}
int main() {
in >> N;
in >> XX.x >> XX.y;
for( int i= 2; i<=N; ++i ) {
PCT a; double r1,r2;
in >> r1 >> r2; a.x= r1; a.y= r2;
v.push_back( a );
if ( Alege_XX( a ) ) {
swap( a, v[0] );
XX= v[0];
}
}
PCT aux= v[0];
v.push_back( v[0] ); /// Adaug la coada primul element
Infas_Convexa( v, r );
out << (int)r.size() << '\n';
for( int i= 0; i<(int)r.size(); ++i ) {
out << fixed << setprecision(12) << r[i].x << ' ' << r[i].y << '\n';
}
return 0;
}