Cod sursa(job #2380423)

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

using namespace std;

const int nmax=120005;

struct numere{double x, y;};

numere v[nmax];
numere st[nmax];
numere dr[nmax];
numere oks[nmax];
numere okd[nmax];

int dir(numere a, numere b, numere c)
{
    double s;
    s=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
    if(s>0)
        s=1;
    if(s<0)
        s=-1;
    int sol=s;
    return sol;
}

int cmp(numere a, numere b)
{
    if(a.y<b.y)
        return 1;
    else if(a.y==b.y && a.x<b.x)
        return 1;
    return 0;
}

int infas(numere v[], numere ok[], int n, int semn)
{
    int i=2,k=2;
    ok[0]=v[0];
    ok[1]=v[1];
    while(i<n)
    {
        while(k>1 && dir(ok[k-2],ok[k-1],v[i])*semn>0)
            k--;
        ok[k]=v[i];
        k++;
        i++;
    }
    return k;
}

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

    scanf("%d", &n);
    for(i=0; i<n; i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v,v+n,cmp);
    k1=k2=1;
    st[0]=v[0];
    dr[0]=v[0];
    for(i=1; i<n-1; i++)
        if(dir(v[0],v[n-1],v[i])>0)
            st[k1++]=v[i];
        else
            dr[k2++]=v[i];
    st[k1++]=v[n-1];
    dr[k2++]=v[n-1];
    k1=infas(st,oks,k1,1);
    k2=infas(dr,okd,k2,-1);
    printf("%d\n",k1+k2-2);
    for(i=0; i<k2-1; i++)
        printf("%lf %lf\n",okd[i].x,okd[i].y);
    for(i=k1-1; i>0; i--)
        printf("%lf %lf\n",oks[i].x,oks[i].y);

    return 0;
}