Cod sursa(job #2304084)

Utilizator vladth11Vlad Haivas vladth11 Data 17 decembrie 2018 15:02:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,stiva[120001],vf;

struct pct{
     double x,y;
}v[120001];
pct rez[120001];
bool cmp(pct a,pct b){
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
bool cmp1(pct a,pct b){
    return (a.x > b.x);
}
double triunghi(pct a,pct b,pct c){
    return (a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y));
}
int main()
{
    int i;
    cin >> n;
    for(i = 1;i <= n;i++){
        cin >> v[i].x >> v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    stiva[++vf] = 1;
    stiva[++vf] = 2;
    for(i = 3;i <= n;i++){
        while(vf > 1 && triunghi(v[stiva[vf - 1]],v[stiva[vf]],v[i]) < 0)
            vf--;
        stiva[++vf] = i;

    }
    int c = 0;
     for(i = 1;i <= vf;i++){
        rez[++c] = v[stiva[i]];
    }
    vf = 0;
    stiva[++vf] = n;
    stiva[++vf] = n-1;
    for(i = n - 2;i >= 1;i--){
        while(vf > 1 && triunghi(v[stiva[vf - 1]],v[stiva[vf]],v[i]) < 0)
            vf--;
        stiva[++vf] = i;
    }
    for(i = 2;i <= vf-1;i++){
        rez[++c] = v[stiva[i]];
    }
    cout << c << "\n";
    for(i = 1;i <= c;i++)
        cout << fixed << setprecision(6) << rez[i].x << " " <<  fixed << setprecision(6) <<(double)rez[i].y << "\n";
    return 0;
}