Cod sursa(job #1325497)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 23 ianuarie 2015 23:54:19
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
 
struct punct{
       double x;
       double y;
};
 
const int MAX_N = 120005;
 
int sol[MAX_N],nr;
punct a[MAX_N];
int i,n;
 
short int semn(const punct &A, const punct &B, const punct &P){
      double x = (B.x*P.y + A.x*B.y + A.y*P.x - B.x*A.y - P.x*B.y - P.y*A.x);
      if(x>0) return 1;
      if(x<0) return (-1);
      return 0;
}

void jarvis_march(punct a[MAX_N], int n, int sol[MAX_N], int &nr){
     int i,poz_min_x,p,q;
     
     poz_min_x=1;
     for(i=1;i<=n;i++)
       if(a[i].x<a[poz_min_x].x) poz_min_x=i;
     
     nr=0;
     sol[++nr]=poz_min_x;
     
     do{
        
        p=sol[nr];
        q=(sol[nr]+1)%n+1;
        for(i=1;i<=n;i++)
          if(semn(a[p], a[q], a[i])<0) 
            q=i;
        
        sol[++nr]=q;
                            
       }while(sol[nr]!=poz_min_x);
     
     --nr;
}

void afisare_solutie(int sol[MAX_N], int nr){
     fo<<nr<<'\n';
     for(i=1;i<=nr;i++)
       fo<<fixed<<setprecision(8)<<a[sol[i]].x<<' '<<a[sol[i]].y<<'\n';
}
 
int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>a[i].x>>a[i].y;
     
    jarvis_march(a,n,sol,nr);
    
    afisare_solutie(sol,nr);
     
    fi.close();
    fo.close();
    return 0;
}