Cod sursa(job #2447722)

Utilizator DavidAA007Apostol David DavidAA007 Data 14 august 2019 13:31:45
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.05 kb
#include<fstream>
#include<iomanip>
#include<iostream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,dim;
double panta,pmin,pmax;
struct punct
{
    double x;
    double y;
};
punct e[120005],infasuratoare[120005],P,Q,minn,maxx,P1,P2,P3,P4;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>e[i].x>>e[i].y;
    P1.x=2147348646;
    P2.x=-2147348646;
    P3.x=-2147348646;
    P4.x=2147348646;
    P1.y=2147348646;
    P2.y=2147348646;
    P3.y=-2147348646;
    P4.y=-2147348646;
    dim=0;
    for(i=1;i<=n;i++)
    {
        if(e[i].x<P4.x)
            P4=e[i];
        if(e[i].x>P2.x)
            P2=e[i];
        if(e[i].y<P1.y)
            P1=e[i];
        if(e[i].y>P3.y)
            P3=e[i];
    }
    for(i=1;i<=n;i++)
    {
        if(e[i].x==P4.x)
            if(e[i].y>P4.y)
                P4=e[i];
        if(e[i].x==P2.x)
            if(e[i].y<P2.y)
                P2=e[i];
        if(e[i].y==P1.y)
            if(e[i].x<P1.x)
                P1=e[i];
        if(e[i].y==P3.y)
            if(e[i].x>P3.x)
                P3=e[i];
    }
    ///cout<<P1.x<<" "<<P1.y<<"\n";
    ///cout<<P2.x<<" "<<P2.y<<"\n";
    ///cout<<P3.x<<" "<<P3.y<<"\n";
    ///cout<<P4.x<<" "<<P4.y<<"\n";
    dim++;
    infasuratoare[dim]=P1;
    P=P1;
    while(! (P.x==P2.x && P.y==P2.y))
    {
        pmin=2147348646;
        panta=0;
        for(i=1;i<=n;i++)
        {
            if(e[i].x>P.x)
            {
                Q=e[i];
                ///verificam daca punctul Q este cel cautat
                ///calculam panta
                panta=(Q.y-P.y)/(Q.x-P.x);
                if(panta<=pmin)
                {
                    pmin=panta;
                    minn=Q;
                }
            }
        }
        P=minn;
        dim++;
        infasuratoare[dim]=P;
        ///cout<<P.x<<" "<<P.y<<"\n";
    }
    while(! (P.x==P3.x && P.y==P3.y))
    {
        pmax=-2147348646;
        panta=0;
        for(i=1;i<=n;i++)
        {
            if(e[i].y>P.y)
            {
                Q=e[i];
                ///verificam daca punctul Q este cel cautat
                ///calculam panta
                if(Q.x-P.x==0)
                    panta=0;
                else
                    panta=(Q.y-P.y)/(Q.x-P.x);
                if(panta>=pmax)
                {
                    pmax=panta;
                    maxx=Q;
                }
            }
        }
        P=maxx;
        dim++;
        infasuratoare[dim]=P;
        ///cout<<P.x<<" "<<P.y<<"\n";
    }
    while(! (P.x==P4.x && P.y==P4.y))
    {
        pmin=2147348646;
        panta=0;
        for(i=1;i<=n;i++)
        {
            if(e[i].x<P.x)
            {
                Q=e[i];
                ///verificam daca punctul Q este cel cautat
                ///calculam panta
                panta=(Q.y-P.y)/(Q.x-P.x);
                if(panta<=pmin)
                {
                    pmin=panta;
                    minn=Q;
                }
            }
        }
        P=minn;
        dim++;
        infasuratoare[dim]=P;
        ///cout<<P.x<<" "<<P.y<<"\n";
    }
    while(! (P.x==P1.x && P.y==P1.y))
    {
        pmax=-2147348646;
        panta=0;
        for(i=1;i<=n;i++)
        {
            if(e[i].y<P.y)
            {
                Q=e[i];
                ///verificam daca punctul Q este cel cautat
                ///calculam panta
                if(Q.x-P.x==0)
                    panta=0;
                else
                    panta=(Q.y-P.y)/(Q.x-P.x);
                if(panta>=pmax)
                {
                    pmax=panta;
                    maxx=Q;
                }
            }
        }
        P=maxx;
        dim++;
        infasuratoare[dim]=P;
        ///cout<<P.x<<" "<<P.y<<"\n";
    }
    infasuratoare[dim].x=0;
    infasuratoare[dim].y=0;
    dim--;
    g<<dim<<"\n";
    for(i=1;i<=dim;i++)
    {
        g<<fixed<<setprecision(6)<<infasuratoare[i].x<<" ";
        g<<fixed<<setprecision(6)<<infasuratoare[i].y<<"\n";
    }
    f.close();
    g.close();
    return 0;
}