Cod sursa(job #1325502)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 24 ianuarie 2015 00:13:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<algorithm>
#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;
}
  
bool comp(const punct &a, const punct &b){
     if(a.x==b.x) return (a.y<b.y);
     else return (a.x<b.x);
}
 
void infasuratoare(punct a[MAX_N], int n, int st[MAX_N], int &k){
     bool viz[MAX_N];
     int i,p;
      
     for(i=1;i<=n;i++) viz[i]=0;
      
     sort(a+1,a+n+1,comp);
      
     st[1]=1; st[2]=2; k=2; 
     viz[1]=0; viz[2]=1;
     for(i=3,p=1; i>0; i+=(p=(i==n)?(-p):(p)))
      if(!viz[i]){
                  while(k>=2 && semn(a[st[k-1]],a[st[k]],a[i])<=0) viz[st[k--]]=0; 
                  st[++k]=i; 
                  viz[i]=1;
                 }
      
     k--;
}
 
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;
      
    infasuratoare(a,n,sol,nr);
     
    afisare_solutie(sol,nr);
      
    fi.close();
    fo.close();
    return 0;
}