Cod sursa(job #2659617)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 17 octombrie 2020 11:17:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#define NMAX 120005
#include <iostream>
#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];

vector <punct> V1, V2;
int n;

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 compare(punct P0, punct P1){
    if(P0.x < P1.x)
        return 1;
    else if(P0.x == P1.x && P0.y < P1.y)
        return 1;
    return 0;
}

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

void afisare(){
    g<<V1.size() + V2.size() - 2<<'\n';
    for(int i=0; i<V1.size()-1; i++)
        g<<fixed<<setprecision(6)<<V1[i].x<<" "<<V1[i].y<<'\n';
    for(int i=0; i<V2.size()-1; i++)
        g<<fixed<<setprecision(6)<<V2[i].x<<" "<<V2[i].y<<'\n';
}

void solve(){
    V1.push_back(P[0]);
    for(int i=1; i<n; i++){
        while(V1.size() > 1 && orientare(V1[V1.size()-2], V1[V1.size()-1], P[i]) < 0)
            V1.pop_back();
        V1.push_back(P[i]);
    }
    V2.push_back(P[n-1]);
    for(int i=n-2; i>=0; i--){
        while(V2.size() > 1 && orientare(V2[V2.size()-2], V2[V2.size()-1], P[i]) < 0)
            V2.pop_back();
        V2.push_back(P[i]);
    }
}


int main()
{
    citire();
    solve();
    afisare();
    return 0;
}