Cod sursa(job #278510)

Utilizator catalina5catalina serban catalina5 Data 12 martie 2009 13:00:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<iostream>
#include<math.h>


using namespace std;

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

struct pct {
    float x,y,d,c;
};
pct s[120001],minn;
int n,h,st[120001],pmin;

void citire () {
    fin>>n;
    minn.x=15000.0,minn.y=15000.0;
    for(int i=1;i<=n;i++) {
        fin>>s[i].x>>s[i].y;
        if(s[i].y<minn.y || (s[i].y==minn.y && s[i].x<minn.x)) {
                minn=s[i];
                pmin=i;
        }
    }
    pct aux=s[1];
    s[1]=s[pmin];
    s[pmin]=aux;
    fin.close();
}

float det(pct minn,pct a,pct b)  {

     return (a.x-minn.x)*(a.y-minn.y)-(b.x-minn.x)*(a.y-minn.y);
}

int cmp(pct a,pct b) {
    return det(minn,a,b)>0;
}

void infasuratoare () {
    sort(s+2,s+n+1,cmp);
    h=2;
    st[1]=1;
    st[2]=2;
    for(int i=3;i<=n;++i) {
         while(h>=2 && det(s[st[h]],s[i],s[st[h-1]])<=0)
             h--;
         st[++h]=i;
         }
}

void afisare () {
    fout<<h<<"\n";
    for(int i=1;i<=h;i++)
        fout<<s[st[i]].x<<" "<<s[st[i]].y<<"\n";
    fout.close();
}

int main () {
    citire();
    infasuratoare();
    afisare();
    return 0;
}