Cod sursa(job #1453454)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 23 iunie 2015 16:25:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#define nmax 120005
#define eps 1e-12
#include <algorithm>
#define x first
#define y second
#include <fstream>
#include <iomanip>

using namespace std;

typedef pair<double,double> punct;
punct v[nmax];
int n,h;
int st[nmax];
bool vs[nmax];

void citeste(){
ifstream fin("infasuratoare.in");
fin>>n;
int i=1;
while(i<=n){
fin>>v[i].x>>v[i].y;
i++;
}
sort(v+1,v+n+1);
}

double cross_product(punct a,punct b,punct c){
   return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

void infasuratoare_convexa(){
h=2;
st[1]=1;
st[2]=2;
vs[2] = true;
for(int i=1,p=1;i>0;i+=(p=(i==n ? -p:p))){
 if(vs[i])continue;
 while(h>=2 && cross_product(v[st[h-1]],v[st[h]],v[i])<eps)vs[st[h--]]=0;
 st[++h] = i;
 vs[i] = 1;
}
ofstream fout("infasuratoare.out");
fout<<h-1<<"\n";
fout << setprecision(6)<<fixed;
for(int i=1;i<h;++i)fout<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}

int main(){
    citeste();
    infasuratoare_convexa();
    return 0;
}