Cod sursa(job #2211121)

Utilizator Vlad_ConstantinVlad Constantin Vlad_Constantin Data 9 iunie 2018 13:51:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <iostream>
#include <algorithm>
#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;
}
bool compare(coordonate b, coordonate c)
{
    return b.y<c.y;
}
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);

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

    }
    h1++;
    h2++;
    stivadr[h1]=v[n]; numara++;
    stivast[h2]=v[n]; numara++;
    numara=numara-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;
}