Cod sursa(job #744883)

Utilizator ion824Ion Ureche ion824 Data 9 mai 2012 22:35:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

#define x first
#define y second

typedef pair<double, double>Point;

const int NMAX = 120005;
const double EPS = 1e-12;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

Point v[NMAX];
bool viz[NMAX];
int st[NMAX],n;

void read(){
    fin>>n;
    for(int i=1;i<=n;++i)fin>>v[i].x>>v[i].y;
}

double det(Point x1,Point x2,Point x3){
       return (x2.x - x1.x) * (x3.y - x1.y) - (x3.x - x1.x) * (x2.y - x1.y); 
       }
       
void convex_hull(){
     int vf = 2,p;
     sort(v+1,v+n+1);
     st[1] = 1; st[2] = 2; 
     viz[2] = 1; p = 1;
     
     int i = 1;
     while(i>0){
            if(!viz[i]){
                  while(vf >=2 && det(v[st[vf-1]],v[st[vf]],v[i])< EPS )  
                       viz[st[vf--]] = 0;
                  st[++vf] = i;
                  viz[i] = 1;     
                       }    
              if(i==n)p=-p;  
              i+=p;          
               }  
     fout<<vf-1<<'\n';  
     fout<< setprecision(6) << fixed;
     for(int i=1;i<vf;++i)
       fout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';           
     }
     
int main(void){
    read();
    convex_hull();
 return 0;   
}