Cod sursa(job #2557207)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 25 februarie 2020 17:11:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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){
    return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool cmp(Punct B, Punct C){
    return (orientare(P0, B, C)<0);
}
void punctMinim(){
    int poz=1;
    for(int i = 2; i<=n; i++)
        if(P[i].x<P[poz].x)
            poz = i;
        else if(P[i].x == P[poz].x && P[i].y < P[poz].y)
            poz = i;
    P0=P[poz];
    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-1], S[nr], 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=nr; i>=1; i--)
        g<<setprecision(9)<<S[i].x<<" "<<S[i].y<<'\n';

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