Pagini recente » Cod sursa (job #344048) | Cod sursa (job #374613) | Cod sursa (job #707859) | Cod sursa (job #1241834) | Cod sursa (job #2890882)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, M;
struct point{
long double x, y;
const bool operator == ( const point& pt ){
return x == pt.x && y == pt.y;
}
friend istream &operator >> ( istream &in, point& pt ) {
in >> pt.x >> pt.y;
return in;
}
friend ofstream &operator << ( ofstream &out, point& pt ){
out << fixed << setprecision(6) << pt.x << ' ' << pt.y << '\n';
return out;
}
}P[120002], A, B;
long long orientation( point P, point Q, point R ){
return (Q.y-P.y) * (R.x-Q.x) - (Q.x-P.x) * (R.y-Q.y);
}
int Query( int lf, int rg, point Q){
if( rg - lf + 1 <= 3 ){
if( orientation(P[lf], P[lf+1], Q ) < 0 && orientation( P[rg], P[rg-1], Q ) > 0 )
return 1;
if( orientation(P[lf], P[lf+1], Q ) > 0 || orientation( P[rg], P[rg-1], Q ) < 0 )
return -1;
return 0;
}
int mid = (lf + rg)/2;
long long val = orientation( P[lf], P[mid], Q );
if( val == 0 ){
if( Q == P[lf] || Q == P[mid] ) return 0;
if( P[lf].x <= Q.x && Q.x <= P[mid].x && P[lf].y <= Q.y && Q.y <= P[mid].y ) return 1;
return -1;
}
if( val < 0 )
return Query( mid, rg, Q );
if( val > 0 )
return Query( lf, mid, Q );
}
bool comp( const point& A, const point& B ){
return orientation( P[1], A, B ) < 0;
}
vector < point > Hull;
int main()
{
fin >> N;
int first = 1;
for( int i = 1; i <= N; ++i ){
fin >> P[i];
if( P[i].x < P[first].x || P[i].x == P[first].x && P[i].x < P[first].x )
first = i;
}
swap( P[1], P[first] );
sort( P+2, P+N+1, comp );
Hull.push_back( P[1] );
Hull.push_back( P[2] );
for( int i = 3; i <= N; ++i ){
A = Hull[Hull.size() - 2];
B = Hull[Hull.size() - 1];
if( orientation( A, B, P[i] ) < 0 )
Hull.push_back( P[i] );
else {
while( orientation( A, B, P[i] ) >= 0 ){
Hull.pop_back();
B = A;
A = Hull[Hull.size() - 2];
}
Hull.push_back( P[i] );
}
}
fout << Hull.size() << '\n';
for( int i = 0; i < Hull.size(); ++i )
fout << Hull[i];
return 0;
}