Cod sursa(job #2538803)

Utilizator TudorCristeaCristea Tudor TudorCristea Data 5 februarie 2020 10:10:56
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.49 kb
#include <algorithm> ///pentru sort();
#include <math.h>    ///pentru sqrt();
#include <iomanip>   ///pentru setprecison();
#include <fstream>
#include <iostream>
using namespace std;

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

struct coord
{
    double x,y;
}p[201],stiva[201];

int T,n,t;

double dist (coord A,coord B)
{
    return sqrt((double)(A.x-B.x)*(double)(A.x-B.x)+(double)(A.y-B.y)*(double)(A.y-B.y));
}

int cmp (coord A,coord B)
{
    if (A.y<B.y)
    {
        return 1;
    }
    if (A.y>B.y)
    {
        return 0;
    }
    if (A.x<B.x)
    {
        return 1;
    }
    return 0;
}

/// returneaza 1 daca A este in stanga fata de dreapta BC
int InStanga (coord A,coord B,coord C)
{
    A.x-=B.x;
    A.y-=B.y;
    C.x-=B.x;
    C.y-=B.y;
    int produs=A.x*C.y-A.y*C.x;
    if (produs<0)
    {
        return 1;
    }
    return 0;
}

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

        t=0;
        for (j=1;j<=n;)
        {
            if (t<=1)
            {
                stiva[++t]=p[j++];
            }
            else
            {
                if (InStanga(p[j],stiva[t-1],stiva[t])==1)
                {
                    stiva[++t]=p[j++];
                }
                else
                {
                    t--;

                }
            }
        }

        double rez1=0.0;
        for (j=1;j<t;++j)
        {
            rez1+=dist(stiva[j],stiva[j+1]);
        }

        ///t=0;
        for (j=n;j>=1;)
        {
            if (t<=1)
            {
                stiva[++t]=p[j--];
            }
            else
            {
                if (InStanga(p[j],stiva[t-1],stiva[t])==1)
                {
                    stiva[++t]=p[j--];
                }
                else
                {
                    t--;

                }
            }
        }

        fout << t << '\n';
        for (i=1;i<=t;++i)
        {
            fout << setprecision(6) << fixed << stiva[i].x << " " << stiva[i].y << '\n';
        }

        double rez2=0.0;
        for (j=1;j<t;++j)
        {
            rez2+=dist(stiva[j],stiva[j+1]);
        }

        double rez=rez1+rez2;
        ///cout << setprecision(2) << fixed << rez << '\n';
    }
    return 0;
}