Cod sursa(job #2535737)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 1 februarie 2020 11:02:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <algorithm>
#define LengthMax 128000

using namespace std;

struct Point {
    double x,y;
};

int pointsLength,solLength;
Point points[LengthMax],sol[LengthMax];

void scanPt(Point&P) {
    scanf("%lf%lf",&P.x,&P.y);
}

void read() {
    int i;
    scanf("%d",&pointsLength);
    for(i=0;i<pointsLength;++i) {
        scanPt(points[i]);
    }
}

bool pointsCmp(Point P1,Point P2) {
    if(P1.x==P2.x) {
        return P1.y<P2.y;
    }
    else {
        return P1.x<P2.x;
    }
}

void addInSol(Point P) {
    sol[solLength++]=P;
}

char trigo(Point P1,Point P2,Point P3) {
    return ((P1.x-P3.x)*(P2.y-P3.y)-(P2.x-P3.x)*(P1.y-P3.y))>=0;
}

void ver() {
    for(;solLength>2;) {
        if(!trigo(sol[solLength-3],sol[solLength-2],sol[solLength-1])) {
            --solLength;
            sol[solLength-1]=sol[solLength];
        }
        else {
            break;
        }
    }
}

void hull() {
    int i;
    addInSol(points[0]);
    for(i=1;i<pointsLength;++i) {
        addInSol(points[i]);
        ver();
    }
    for(i=pointsLength-2;i>=0;--i) {
        addInSol(points[i]);
        ver();
    }
}

void printPt(Point P) {
    printf("%.6f %.6f\n",P.x,P.y);
}

void display() {
    int i;
    --solLength;
    printf("%d\n",solLength);
    for(i=0;i<solLength;++i) {
        printPt(sol[i]);
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    read();
    sort(points,points+pointsLength,pointsCmp);
    hull();
    display();
    return 0;
}