Cod sursa(job #2202958)

Utilizator VasilescuVasilescu Eliza Vasilescu Data 10 mai 2018 16:07:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

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

 struct punct
{
    double x, y;
};
punct stiva[120001],p[120001],sol[120001];

bool cmp (punct a, punct b) {
    if (a.x < b.x)
        return true;
    else if (a.x > b.x)
        return false;
    else if (a.y < b.y)
        return true;
    else
        return false;
}

double aria(punct a, punct b, punct c){
    return (a.x-b.x)*(a.y+b.y)+(b.x-c.x)*(b.y+c.y)+(c.x-a.x)*(c.y+a.y);
}

int main()
{
    int n, vf, cvf;
    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>p[i].x>>p[i].y;
    }
    sort(p+1, p+n+1, cmp);

    vf=0;
    stiva[++vf]=p[1];
    for(int i=2; i<=n; i++){
        while(vf>1 && aria(stiva[vf-1], stiva[vf], p[i])<0){
            vf--;
        }
        stiva[++vf]=p[i];
    }
    for(int i=1; i<vf; i++)
        sol[i] = stiva[i];
    cvf=vf;

    vf=0;
    stiva[++vf]=p[n];
    for(int i=n-1; i>=1; i--){
        while(vf>1 && aria(stiva[vf-1], stiva[vf], p[i])<0){
            vf--;
        }
        stiva[++vf]=p[i];
    }

    fout<<cvf+vf-2<<"\n";
    for (int i = 2; i < cvf; i++)
        fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<"\n";
    for (int i = 1; i < vf; i++)
        fout<<fixed<<setprecision(6)<<stiva[i].x<<" "<<stiva[i].y<<"\n";
        fout<<fixed<<setprecision(6)<<sol[1].x<<" "<<sol[1].y<<"\n";
    return 0;
}