Pagini recente » Cod sursa (job #2949562) | Cod sursa (job #3313761) | Cod sursa (job #3334615) | Cod sursa (job #3309731) | Cod sursa (job #3355628)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct ura{
double x, y;
bool parte; ///true pentru dr-jos, false pentru st-sus
} v[120001], a, b;
int st[120001];
bool cmp( ura a, ura b ){
if( a.x < b.x )
return true;
if( a.x > b.x )
return false;
if( a.y < b.y )
return true;
return false;
}
double 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;
} ///functia returneaza dublul arii unui triunghi
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int main()
{
int n, i;
cin>>n;
for( i = 1; i <= n; i++ )
cin>>v[i].x>>v[i].y;
sort( v + 1, v + n + 1, cmp );
///determinam partea fiecarui element
//v[1] si v[n] sunt exceptiile, fiind in ambele parti simultan
a=v[1];
b=v[n];
for( i = 2; i <= n - 1; i++ ){
//daca aria < 0 atunci e in dr/josul liniei
//aria != 0 pentru ca nu exista puncte coliniare
//daca aria > 0 atunci e in st/susul liniei
if( arie(a,b,v[i]) < 0 )
v[i].parte=true;
else
v[i].parte=false;
}
///acum facem partea true ( dr-jos )
v[n].parte=true;
st[1]=1;
int k=1;
for( i = 2; i <= n; i++ )
if( v[i].parte == true ){
while( k >= 2 && arie(v[st[k-1]],v[st[k]],v[i]) < 0 )
k--;
st[++k]=i;
}
///acum facem parte false ( st-sus )
int cpk=k;
st[k]=n;
v[1].parte=false;
for( i = n - 1; i >= 1; i-- )
if( v[i].parte == false ){
while( k >= cpk + 1 && arie(v[st[k-1]],v[st[k]],v[i]) < 0 )
k--;
st[++k]=i;
}
cout<<k-1<<'\n'; ///st[k]==1
for( i = 1; i < k; i++ )
cout<<fixed<<setprecision(6)<<v[st[i]].x<<' '<<v[st[i]].y<<' '<<'\n';
return 0;
}