Cod sursa(job #1135921)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 8 martie 2014 15:57:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define Inf 2000000000
using namespace std;

struct element {double x,y;};
element Punct[120010],Stiva[120010];
int N,nrelemstiva;


void citire() {

    ifstream in("infasuratoare.in");
    int i,aux;
    double minimx=Inf,minimy=Inf;
    in>>N;
    for(i=1;i<=N;i++) {

        in>>Punct[i].x>>Punct[i].y;

        if(Punct[i].x<minimx) {
            minimx=Punct[i].x;
            minimy=Punct[i].y;
            aux=i;
        }

        if(Punct[i].x==minimx && Punct[i].y<minimy) {
            minimy=Punct[i].y;
            aux=i;
        }
    }
    swap(Punct[1],Punct[aux]);
    in.close();

}

bool cmp(element A, element B) {
    return ( ( (A.x - Punct[1].x)*(B.y - Punct[1].y)-(A.y - Punct[1].y)*(B.x - Punct[1].x))>0 );
}

void solve() {

    int i;
    sort(Punct+2,Punct+N+1,cmp);

    Stiva[1]=Punct[1];
    Stiva[2]=Punct[2];
    nrelemstiva=2;
    for(i=3;i<=N;i++) {
        while(nrelemstiva>=2 &&( ( Stiva[nrelemstiva].x - Stiva[nrelemstiva-1].x)*(Punct[i].y - Stiva[nrelemstiva-1].y)-(Stiva[nrelemstiva].y - Stiva[nrelemstiva-1].y)* (Punct[i].x - Stiva[nrelemstiva-1].x))<0)
            nrelemstiva--;
        Stiva[++nrelemstiva]=Punct[i];
    }
}

void afisare() {

    ofstream out("infasuratoare.out");
    int i;
    out<<nrelemstiva << "\n";
    for (i=1;i<=nrelemstiva;i++)
        out<<fixed<<setprecision(6)<<Stiva[i].x<<" "<< Stiva[i].y<<"\n";

    out.close();

}


int main() {

    citire();
    solve();
    afisare();
    return 0;

}