Cod sursa(job #3223501)

Utilizator DaniMoloMolodet Andrei Daniel DaniMolo Data 13 aprilie 2024 12:36:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct pct{
    double x, y;
};

const int mxN = 120001;

int n, k = 0;
pct sir[mxN], ans[mxN];

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

double orientare(pct a, pct b, pct c){
    //mBC > mAB
    //(yc - yb) / (xc - xb) > (yb - ya) / (xb - xa)
    //(yc - yb) * (xb - xa) - (xc - xb) * (yb - ya) > 0

    return (c.y - b.y) * (b.x - a.x) - (b.y - a.y) * (c.x - b.x);
}

bool crtSort(pct a, pct b){
    if(orientare(sir[1], a, b) > 0)
        return true;
    return false;
}

void sortare(){
    int indMin = 1;
    for(int i = 2; i <= n; i++)
        if(sir[indMin].y > sir[i].y || (sir[indMin].y == sir[i].y && sir[indMin].x > sir[i].x))
            indMin = i;

    swap(sir[indMin], sir[1]);
    sort(sir + 2, sir + 1 + n, crtSort);

    /*
    for(int i = 2; i <= n; i++){
        double t = (sir[i].y - sir[1].y) / (sir[i].x - sir[1].x);
        fout << t << "\n";
    }
    */
}

void convexHull(){
    ans[++k] = sir[1];
    ans[++k] = sir[2];

    for(int i = 3; i <= n; i++){
        while(orientare(ans[k], ans[k - 1], sir[i]) > 0){
            k--;
        }

        ans[++k] = sir[i];
    }
}

void afisare(){
    fout << k << "\n";
    for(int i = 1; i <= k; i++){
        fout << setprecision(20) << ans[i].x << " " << ans[i].y << "\n";
    }
}

int main()
{
    citire();
    sortare();
    convexHull();
    afisare();

    return 0;
}