Cod sursa(job #2286776)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 20 noiembrie 2018 18:53:28
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stack>
#define eps 1e-14

using namespace std;

struct punct{
    double x,y;
    void print()
    {
        printf("%.6lf %.6lf\n",x,y);
    }
};

vector<punct>path,v,sol;
stack<int>st;

double dist(punct a,punct b)
{
    return sqrt(1.0*(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y)));
}

int orientare(punct a,punct b,punct c)
{
    double val = 1.0*(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
    if(val >= -eps && val <= eps)
        return 0;
    if(val < -eps)
        return -1;
    else
        return 1;
}

void interschimba(punct a,punct b)
{
    punct aux;
    aux = a;
    a = b;
    b = aux;
}

int penult()
{
    int temp = st.top();
    int aux;
    st.pop();
    aux = st.top();
    st.push(temp);
    return aux;
}

punct start;

bool cmp(punct a,punct b)
{
    if(orientare(start,a,b) == 0)
        return dist(start,a)<dist(start,b);
    if(orientare(start,a,b) == 1)
        return 0;
    return 1;
}


int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,x,y;
    scanf("%d",&n);
    int pos;
    double xm=2000000000,ym=2000000000;
    for(int i = 1 ; i <= n ; i ++)
    {
        scanf("%lf%lf",&x,&y);
        punct temp;
        temp.x = x;
        temp.y = y;
        v.push_back(temp);
        if(ym - y > eps)
        {
            ym = y;
            xm = x;
            pos = i;
            continue;
        }
        if(fabs(ym-y)<eps)
        {
            if(fabs(xm-x))
            {
                x = xm;
                y = ym;
                pos = i;
                continue;
            }
        }
    }
    interschimba(v[0],v[pos-1]);
    start = v[0];
    sort(v.begin()+1,v.end(),cmp);
    int dim = -1;
    path.push_back(start);
    for(int i = 1 ; i < v.size() ; i++)
    {
        while(i < v.size()-1 &&  orientare(start,v[i],v[i+1]) == 0)
            i++;
        path.push_back(v[i]);
    }
    st.push(0);
    int i = 1;
    while(i < path.size())
    {
        if(orientare(path[penult()],path[st.top()],path[i]) == 1)
            st.push(i++);
        else
            st.pop();
    }
    while(!st.empty())
    {
        sol.push_back(path[st.top()]);
        st.pop();
    }
    printf("%d\n",sol.size());
    for(int i = 0 ; i < sol.size() ; i++)
        sol[i].print();
    return 0;
}