Pagini recente » Cod sursa (job #3276663) | Cod sursa (job #370676) | Cod sursa (job #2742527) | Cod sursa (job #1253921) | Cod sursa (job #3288851)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
#define MAXN 120000
struct ura {
double x, y;
int plan;
} v[MAXN + 1], a, b;
ura st[MAXN + 1];
bool cmp( ura a, ura b ) {
return ( a.x < b.x || ( a.x == b.x && a.y < b.y ) );
}
int arie( ura a, ura b, ura c ) {
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
int main() {
int n, i, niv, niv2;
fin >> n;
for( i = 1; i <= n; i++ )
fin >> v[i].x >> v[i].y;
sort( v + 1, v + n + 1, cmp );
a = v[1];
b = v[n];
for( i = 2; i <= n - 1; i++ )
if( arie( a, b, v[i] ) > 0 )
v[i].plan = 1;
else if( arie( a, b, v[i] ) < 0 )
v[i].plan = 2;
niv = 0;
st[++niv] = v[1];
for( i = 2; i <= n; i++ ) {
if( v[i].plan < 2 ) { //0 sau 1
while( niv > 1 && arie( st[niv - 1], st[niv], v[i] ) > 0 )
niv--;
st[++niv] = v[i];
}
}
niv2 = niv;
st[niv] = v[n];
for( i = n - 1; i > 0; i-- ) {
if( ( v[i].plan & 1 ) == 0 ) { //0 sau 2
while( niv > niv2 && arie( st[niv - 1], st[niv], v[i] ) > 0 )
niv--;
st[++niv] = v[i];
}
}
niv--;
fout << niv << '\n';
for( i = niv; i > 0; i-- )
fout << fixed << setprecision( 6 ) << st[i].x << ' ' << st[i].y << '\n';
return 0;
}