Cod sursa(job #2535652)

Utilizator alex02Grigore Alexandru alex02 Data 1 februarie 2020 10:18:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct point{
    double x,y;
}puncte[120005];
int n;
bool compare(point x, point y){
    if(x.x<y.x)
        return true;
    if(x.x==y.x)
        return x.y<y.y;
    return false;
}

void citire(){
    f>>n;
    for (int i = 0; i < n; ++i) {
        f>>puncte[i].x>>puncte[i].y;
    }
    sort(puncte,puncte + n,compare);
}

bool sens_trigo(point a, point b, point c){
    double det=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    return det>=0;
}

void afis(point a){
    g<<setprecision(6)<<fixed<<a.x<<" "<<a.y<<endl;
}

void rezolvare(){
    point a=puncte[0],b=puncte[1];

    for(int i=2; i<n; i++){
        if(!sens_trigo(a,b,puncte[i])){
            b=puncte[i];
        }
        else {
            afis(b);
            a=b;
            b=puncte[i];
        }
    }
    a=puncte[n-1];
    afis(a);
    b=puncte[n-2];
    for(int i=n-3; i>=0; i--){
        if(!sens_trigo(a,b,puncte[i])){
            b=puncte[i];
        }
        else {
            afis(b);
            a=b;
            b=puncte[i];
        }
    }
    afis(puncte[0]);

}
int main() {
    citire();
    rezolvare();
    return 0;
}