Cod sursa(job #2556981)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 25 februarie 2020 13:34:12
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
/**
Fara puncte coliniare
**/
#define NMAX 120005
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");


struct Punct{
    double x, y;
}P[NMAX], P0;
Punct S[NMAX];
int n, nr=0;

double orientare(Punct A, Punct B, Punct C){
    double nr = (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
    return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool cmp(Punct p0, Punct p1){
    return orientare(P0, p0, p1)<0;
}
void punctMinim(){
    int poz=1;
    for(int i = 2; i<=n; i++)
        if(P[i].y<P[poz].y)
            poz = i;
        else if(P[i].y == P[poz].y && P[i].x<P[poz].x)
            poz = i;
    swap(P[1], P[poz]); /// imi aduc pe prima pozitie elementul minim
    sort(P+2, P+n+1, cmp);


}

void construiesc_infas(){
    S[nr++]=P[1];
    S[nr++]=P[2];

    for(int i=3; i<=n; i++){
        while(nr>2 && orientare(S[nr-2], S[nr-1], P[i])>0)
            nr--;
        S[nr++] = P[i];
    }
}

void citire(){
    f>>n;
    for(int i=1; i<=n; i++){
        f>>P[i].x>>P[i].y;
    }

}

void afisare(){
    g<<fixed;
    g<<nr<<'\n';
    for(int i=0; i<nr; i++)
        g<<setprecision(9)<<S[i].x<<" "<<S[i].y<<'\n';

}
int main()
{
    citire();
    punctMinim();
    construiesc_infas();
    afisare();
    return 0;
}