Cod sursa(job #2984962)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 25 februarie 2023 12:27:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

double ariemax;

struct punct{

    double x , y;

};

double orientation( punct a, punct b, punct c ){

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

}

int n;

punct puncte[20];

bool cmp(punct a , punct b){

  return orientation(puncte[1],a,b)<0;

}

void infasuratoare(){

    int minp = 1;

    for(int i = 2 ; i <= n ; i++){

        if( puncte[minp].y > puncte[i].y || (puncte[minp].y == puncte[i].y && puncte[minp].x < puncte[i].x)){

            minp = i;
        }
    }

    swap(puncte[minp],puncte[1]);

    sort(puncte + 2 , puncte + n + 1 ,cmp);

    vector <punct> hull;

    hull.push_back(puncte[1]);
    hull.push_back(puncte[2]);

    for(int i = 3 ; i <= n ; i++){

        while( hull.size() >= 2 && orientation(hull[hull.size()-2] , hull.back() ,puncte[i])>=0) hull.pop_back();

        hull.push_back(puncte[i]);
    }

    double arie;

    for(int i = 1 ; i <= n ; i++){

        cout << puncte[i].x << ' ' << puncte[i].y << '\n';
    }

    cout << hull.size() << '\n';

    for(auto it : hull){

        cout << fixed << setprecision(13) << it.x << ' ' << it.y;

        cout << '\n';
    }

}

int main(){


    cin >> n;

    for(int i = 1 ; i <= n ;i++){

        cin >> puncte[i].x >> puncte[i].y;
    }


    infasuratoare();

    return 0;
}