Cod sursa(job #2211093)

Utilizator Vlad_ConstantinVlad Constantin Vlad_Constantin Data 9 iunie 2018 13:16:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <stdio.h>
#include <iostream>
#define NMAX 120001
using namespace std;
struct coordonate
{
    double x,y;
    int pozitie;
};
coordonate v[NMAX];
coordonate primul,ultimul;
coordonate stivadr[NMAX],stivast[NMAX];

int arie(coordonate a)
{
    float arie1;
    int valid;
    arie1=primul.x*ultimul.y+ultimul.x*a.y+a.x*primul.y-a.x*ultimul.y-primul.x*a.y-ultimul.x*primul.y;
    if(arie1<0)
        valid=0;
    if(arie1>0)
        valid=1;
    return valid;
    // valid == 0 dreapta;
    // valid == 1 stanga;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    bool ok = true;
    while(ok)
    {
        ok=false;
        for(i=1;i<=n-1;i++)
            if(v[i].y>v[i+1].y)
            {
                swap(v[i],v[i+1]);
                ok=true;
            }
            if(v[i].y==v[i+1].y&&v[i].x>v[i+1].x)
                {
                    swap(v[i],v[i+1]);
                    ok=true;
                }
    }
    primul.x=v[1].x;    primul.y=v[1].y;
    ultimul.x=v[n].x;   ultimul.y=v[n].y;

    for(i=1; i<=n;i++)
        v[i].pozitie=arie(v[i]);
    v[1].pozitie=2;
    v[n].pozitie=2;
    // in dreapta
    int numara;
    int h1=1,h2=1;
    stivadr[h1]=primul;
    stivast[h2]=primul;
    for(i=1;i<=n-1;i++)
    {
        if(v[i].pozitie==0)
        {
            while(stivadr[h1].x<v[i].x && h1>1)
                h1--;
            h1++;
            stivadr[h1]=v[i];
        }
        else
        {
            while(stivast[h2].x>v[i].x && h2>1)
                h2--;
            h2++;
            stivast[h2]=v[i];
        }

    }
    h1++;
    h2++;
    stivadr[h1]=v[n];
    stivast[h2]=v[n];
    numara=h2+h1-2;
    printf("%d\n", numara);
    for(i=1;i<=h1-1;i++)
        printf("%f %f\n", stivadr[i].x, stivadr[i].y);
    for(i=h2;i>=2;i--)
        printf("%f %f\n", stivast[i].x, stivast[i].y);
    return 0;
}