Cod sursa(job #2538827)

Utilizator TudorCristeaCristea Tudor TudorCristea Data 5 februarie 2020 10:36:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 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
{
    int 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 j;
        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--;

                }
            }
        }

        --t;
        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-1 << '\n';
        for (j=1;j<t;++j)
        {
            fout << stiva[j].x << " " << stiva[j].y << '\n';
        }
    fin.close();
    fout.close();
    return 0;
}