Cod sursa(job #2380200)

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

using namespace std;

const int nmax=120000;

struct coordonate{double x, y;};
coordonate v[nmax];
vector <pair <double, double> > st;
vector <pair <double, double> > dr;

deque <int> stiva;
deque <pair <double, double> > rasp;

bool cmp(coordonate a, coordonate b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
bool semn(double ax, double ay, double bx, double by, double cx, double cy){return ax*by+bx*cy+cx*ay-by*cx-cy*ax-ay*bx>=0;}

void infasuratoare(bool sem, double ax, double ay)
{
    double a1x, a1y, a2x, a2y;
    a1x=ax;
    a1y=ay;
    if(sem==1)
    {
        a2x=dr[0].first;
        a2y=dr[0].second;
        for(int i=1;i<dr.size();i++)
        {
            if(semn(a1x, a1y, dr[i].first, dr[i].second, a2x, a2y)!=sem)
            {
                stiva.push_back(i);
                a1x=a2x;
                a1y=a2y;
                a2x=dr[i].first;
                a2y=dr[i].second;
            }
            else
            {
                stiva.pop_back();
                stiva.push_back(i);
                a2x=dr[i].first;
                a2y=dr[i].second;
            }
        }
    }
    else
    {
        a2x=st[0].first;
        a2y=st[0].second;
        for(int i=1;i<dr.size();i++)
        {
            if(semn(a1x, a1y, st[i].first, st[i].second, a2x, a2y)!=sem)
            {
                stiva.push_back(i);
                a1x=a2x;
                a1y=a2y;
                a2x=st[i].first;
                a2y=st[i].second;
            }
            else
            {
                stiva.pop_back();
                stiva.push_back(i);
                a2x=st[i].first;
                a2y=st[i].second;
            }
        }
    }
}

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

    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[1].x, v[1].y, v[i].x, v[i].y, v[n].x, v[n].y)==1)
            dr.push_back(make_pair(v[i].x, v[i].y));
        else
            st.push_back(make_pair(v[i].x, v[i].y));
    }
    rasp.push_back(make_pair(v[0].x, v[0].y));
    infasuratoare(1, v[0].x, v[0].y);
    while(stiva.size())
    {
        rasp.push_back(st[stiva.front()]);
        stiva.pop_front();
    }
    rasp.push_back(make_pair(v[n].x, v[n].y));
    infasuratoare(0, v[0].x, v[0].y);
    while(stiva.size())
    {
        rasp.push_back(st[stiva.back()]);
        stiva.pop_back();
    }
    printf("%d\n", rasp.size());
    for(int i=0;i<rasp.size();i++)
        printf("%d %d\n", rasp[i].first, rasp[i].second);

    return 0;
}