Cod sursa(job #2878655)

Utilizator VINTREXNume complet VINTREX Data 27 martie 2022 14:01:07
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <bits/stdc++.h>

using namespace std;

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

struct puncte
{
    double x, y;
} punct[120001], stiva_dr[120001], stiva_st[120001], stanga[120001], dreapta[120001];


double arie(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return (x1*y2+x2*y3+x3*y1-y3*x1-y2*x3-x2*y1)/2.0;
}
double comparare(puncte a, puncte b)
{
    if (a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}


int  main()
{
    int n;
    fin >> n;
    for (int i=1; i<=n; i++)
        fin >> punct[i].x >> punct[i].y;
    sort(punct + 1, punct + n + 1, comparare);
    int contor_dr=0, contor_st=0, k=0, l=0;
    for(int i=1; i<=n; i++)
        if(arie(punct[1].x, punct[1].y, punct[n].x, punct[n].y, punct[i].x, punct[i].y)>0)
            dreapta[++contor_dr]=punct[i];
        else
            if(arie(punct[1].x, punct[1].y, punct[n].x, punct[n].y, punct[i].x, punct[i].y)<0)
                stanga[++contor_st]=punct[i];
                /*
    cout << '\n';
    for(int i=1; i<=contor_st; i++)
        cout << stanga[i].x <<' '<<stanga[i].y<<'\n';
        */
    stiva_dr[++k]=punct[1];
    stiva_dr[++k]=dreapta[1];
    for(int i=2; i<=contor_dr; i++)
    {
        while(arie(stiva_dr[k-1].x, stiva_dr[k-1].y, stiva_dr[k].x, stiva_dr[k].y, dreapta[i].x, dreapta[i].y)>0 && k>=2)
            k--;
        stiva_dr[++k]=dreapta[i];
    }
    /*
    cout << '\n';
    for(int i=1; i<=k; i++)
        cout << stiva_dr[i].x <<' '<< stiva_dr[i].y <<'\n';
        */
    stiva_st[++l]=punct[1];
    stiva_st[++l]=stanga[1];
    for(int i=2; i<=contor_st; i++)
    {
        while(arie(stiva_st[l-1].x, stiva_st[l-1].y, stiva_st[l].x, stiva_st[l].y, stanga[i].x, stanga[i].y)<0 && l>=2)
            l--;
        stiva_st[++l]=stanga[i];
    }
    /*
    cout << '\n';
    for(int i=1; i<=l; i++)
        cout << stiva_st[i].x <<' '<< stiva_st[i].y <<'\n';
        */
    fout << k+l <<'\n';
    for(int i=1; i<=l; i++)
        fout <<fixed<<setprecision(12)<< stiva_st[i].x <<' '<< stiva_st[i].y <<'\n';
    fout << punct[n].x <<' '<< punct[n].y <<'\n';
    for(int i=k; i>1; i--)
        fout << stiva_dr[i].x <<' '<<stiva_dr[i].y <<'\n';
}