Cod sursa(job #2380409)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 14 martie 2019 21:18:14
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax=120005;

struct numere
{
    double x;
    double y;
};

numere v[nmax];
deque <numere> st;
deque <numere> dr;

deque <int> coada;
deque <numere> rasp;

bool cmp(numere a, numere b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
short semn(double x1, double y1, double x2, double y2, double x3, double y3)
{
    if(x1*y2+x2*y3+x3*y1-y2*x3-y3*x1-y1*x2>=0)
        return 1;
    return -1;
}
void infasuratoare(int sem)
{
    int x1, y1, x2, y2;
    x1=v[1].x;
    y1=v[1].y;
    if(sem==1)
    {
        x2=dr[0].x;
        y2=dr[0].y;
        coada.push_back(0);
        for(int i=1;i<dr.size();i++)
        {
            if(semn(x1, y1, dr[i].x, dr[i].y, x2, y2)!=sem)
            {
                x1=x2;y1=y2;
                x2=dr[i].x;y2=dr[i].y;
                coada.push_back(i);
            }else
            {
                x2=dr[i].x;y2=dr[i].y;
                coada.pop_back();
                coada.push_back(i);
            }
        }
    }
    else
    {
        x2=st[0].x;
        y2=st[0].y;
        coada.push_back(0);
        for(int i=1;i<dr.size();i++)
        {
            if(semn(x1, y1, st[i].x, st[i].y, x2, y2)!=sem)
            {
                x1=x2;y1=y2;
                x2=st[i].x;y2=st[i].y;
                coada.push_back(i);
            }else
            {
                x2=st[i].x;y2=st[i].y;
                coada.pop_back();
                coada.push_back(i);
            }
        }
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n;

    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v+1, v+n+1, cmp);
    for(int i=2;i<n;i++)
    {
        if(semn(v[0].x, v[0].y, v[i].x, v[i].y, v[n].x, v[n].y)==1)
            dr.push_back(v[i]);
        else
            st.push_back(v[i]);
    }
    infasuratoare(1);
    while(!coada.empty())
    {
        rasp.push_back(dr[coada.front()]);
        coada.pop_front();
    }
    infasuratoare(-1);
    while(!coada.empty())
    {
        rasp.push_back(st[coada.back()]);
        coada.pop_back();
    }
    rasp.push_back(v[n]);
    printf("%d\n", rasp.size());
    for(int i=0;i<rasp.size();i++)
        printf("%lf %lf\n", rasp[i].x, rasp[i].y);

    return 0;
}