Cod sursa(job #1647301)

Utilizator bullseYeIacob Sergiu bullseYe Data 10 martie 2016 19:53:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120010
using namespace std;

struct pct{
    double x, y;
};

pct P[NMAX], S[NMAX];
int vfS, n;

void citire();
void Graham();
inline bool cmp (const pct&, const pct&);
inline double prodi (const pct&, const pct&, const pct&);
void afisare();

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

void citire(){
    int i;
    FILE*fin=fopen ("infasuratoare.in", "r");

    fscanf(fin, "%d", &n);
    for (i=1; i<=n; ++i)
        fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);

    fclose(fin);
    return;
}

void Graham(){
    pct xy=P[1];
    int vfmin=1, i;

    for (i=2; i<=n; ++i)
    if (P[i].y<xy.y || (P[i].y==xy.y && P[i].x<xy.x)){
        xy=P[i];
        vfmin=i;
    }

    swap (P[vfmin], P[1]);
    sort (P+2, P+n+1, cmp);

    S[1]=P[1]; S[2]=P[2]; vfS=2;

    for (i=3; i<=n; ++i){
        while (vfS>1 && prodi(S[vfS-1], S[vfS], P[i])<=0)
            --vfS;
        S[++vfS]=P[i];
    }
    return;
}

inline double prodi (const pct &a, const pct &b, const pct &c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    //a-b-c
    //returneaza o valoare pozitiva daca in b se face o intoarcere la stanga
    //val negativa altfel
}

inline bool cmp (const pct &a, const pct &b){
    return prodi(P[1], a, b)>0;
}

void afisare(){
    FILE*fout=fopen ("infasuratoare.out", "w");
    int i;

    fprintf(fout, "%d\n", vfS);

    for (i=1; i<=vfS; ++i)
        fprintf(fout, "%f %f\n", S[i].x, S[i].y);

    fclose(fout);
    return;
}