Cod sursa(job #1017559)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 octombrie 2013 21:54:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#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);
}