Pagini recente » Cod sursa (job #3298571) | Cod sursa (job #3295476) | Cod sursa (job #3296115) | Cod sursa (job #3297337) | Cod sursa (job #3297351)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120'000;
const double EPS = 0.001;
complex <double> v[NMAX + 1];
bool isZero( double a ) {
return abs( a ) <= EPS;
}
bool eq( double a, double b ) {
return isZero( a - b );
}
double cross( complex<double> a, complex<double> b ) {
return a.real() * b.imag() - a.imag() * b.real();
}
double det( complex<double> a, complex<double> b, complex<double> c ) {
return cross( b - a, c - a );
}
int main() {
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
int n;
fin >> n;
for ( int i = 0; i < n; i ++ ) {
double x, y;
fin >> x >> y;
v[i] = {x, y};
}
sort( v, v + n, []( complex <double> a, complex <double> b ) {
if ( a.real() != b.real() ) return a.real() <= b.real();
return a.imag() <= b.imag();
} );
sort( v + 1, v + n, [&]( complex <double> a, complex <double> b ) {
a -= v[0];
b -= v[0];
double aux1 = a.imag() * b.real(), aux2 = b.imag() * a.real();
if ( eq( aux1, aux2 ) ) {
if ( !eq( a.real(), b.real() ) ) return a.real() <= b.real();
return a.imag() <= b.imag();
}
return aux1 < aux2;
} );
deque <complex<double>> st;
for ( int i = 0; i < n; i ++ ) {
while ( st.size() >= 2 && det( st[st.size() - 2], st[st.size() - 1], v[i] ) < 0 ) st.pop_back();
st.push_back( v[i] );
}
fout << st.size() << '\n';
fout << fixed << setprecision( 12 );
for ( auto x : st ) {
fout << x.real() << ' ' << x.imag() << '\n';
}
return 0;
}