Pagini recente » Cod sursa (job #2561092) | Cod sursa (job #1172273) | Cod sursa (job #573210) | Cod sursa (job #289357) | Cod sursa (job #1017559)
#include<iomanip>
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
const long double inf=1e+15;
struct punct {long double x,y,tan; };
punct a[120005],st[120005],ps;
int n,i,lev;
bool cmp( punct a, punct b) { return(a.tan<b.tan); }
long double det(punct a, punct b, punct c) { return( (long double) (a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-c.y*a.x-a.y*b.x) ); }
int main(void) {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n; lev=0; ps.x=inf; ps.y=inf;
for (i=1; i<=n; ++i) {
cin>>a[i].x>>a[i].y;
if ( (a[i].x<ps.x)||(a[i].x==ps.x&&a[i].y<ps.y) ) ps=a[i];
}
for (i=1; i<=n; ++i)
if (a[i].x!=ps.x) a[i].tan=(a[i].y-ps.y)/(a[i].x-ps.x);
else if (ps.x==a[i].x&&a[i].y!=ps.y) a[i].tan=inf;
else a[i].tan=-inf;
sort(a+1,a+n+1,cmp);
lev=2; st[1]=ps; st[2]=a[2];
for (i=3; i<=n; ++i){
while ( det(st[lev-1],st[lev],a[i])<0 && lev>=2 ) --lev;
++lev; st[lev]=a[i];
}
cout<<lev<<"\n";
for (i=1; i<=lev; ++i) cout<<setprecision(6)<<fixed<<st[i].x<<" "<<st[i].y<<"\n";
return(0);
}