Cod sursa(job #2883372)

Utilizator irina_barbu29Irina Barbu irina_barbu29 Data 1 aprilie 2022 14:25:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.21 kb
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<iostream>
#define MAX 1000000000

using namespace std;

struct punct
{
    double x,y;
    int parte;
}v[120005];

int st[120005];

double arie(punct a, punct b, punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}

bool cmp(punct a, punct b)
{
    if(a.y<b.y)
        return true;
    else
        if(a.y>b.y)
            return false;
        else
            return (a.x<b.x);
}

int main()
{
    double maxx=0, maxy=0, minx=MAX+MAX+100, miny=MAX+MAX+100;
    int poz,i,n,pozmin,pozmax;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(miny>v[i].y)
        {
            pozmin=i;
            minx=v[i].x;
            miny=v[i].y;
        }
        else
            if(miny==v[i].y)
                if(v[i].x<minx)
                {
                    pozmin=i;
                    minx=v[i].x;
                    miny=v[i].y;
                }
        if(maxy<v[i].y)
        {
            pozmax=i;
            maxx=v[i].x;
            maxy=v[i].y;
        }
        else
            if(maxy==v[i].y)
                if(v[i].x<minx)
                {
                    pozmax=i;
                    maxx=v[i].x;
                    maxy=v[i].y;
                }
    }
    for(i=1; i<=n; i++)
        if(i!=pozmin&&i!=pozmax)
            if(arie(v[pozmin],v[pozmax],v[i])<0)
                v[i].parte=1;
            else
                v[i].parte=-1;
    sort(v+1,v+n+1,cmp);
    pozmin=1;
    pozmax=n;
    for(i=1; i<=n; i++)
        if(i!=pozmin&&i!=pozmax)
            if(arie(v[pozmin],v[pozmax],v[i])<0)
                v[i].parte=1;
            else
                v[i].parte=-1;
    int k;
    v[1].parte=-1;
    v[n].parte=1;
    st[1]=1;
    i=2;
    while(v[i].parte==-1&&i<n)
        i++;
    st[2]=i;
    k=2;
    int p;
    double a;
    p=v[st[2]].parte;
    for(i=i+1; i<=n; i++)
        if(v[i].parte==p)
        {
            a=arie(v[st[k-1]],v[st[k]],v[i]);
            while(a*v[i].parte<0&&k>0)
            {
                k--;
                a=arie(v[st[k-1]],v[st[k]],v[i]);
            }
            k++;
            st[k]=i;
        }
    /*a=arie(v[st[k-1]],v[st[k]],v[n]);
    while(a*v[n].parte<=0&&k>0){
    k--;
    a=arie(v[st[k-1]],v[st[k]],v[n]);
    }
    st[++k]=n;*/
    i=n-1;
    p=-1;
    while(v[i].parte==1&&i>1)
        i--;
    k++;
    st[k]=i;
    for(i=i-1; i>=2; i--)
        if(v[i].parte==p)
        {
            a=arie(v[st[k-1]],v[st[k]],v[i]);
            while(a*v[i].parte>0&&k>0)
            {
                k--;
                a=arie(v[st[k-1]],v[st[k]],v[i]);
            }
            k++;
            st[k]=i;
        }
    a=arie(v[st[k-1]],v[st[k]],v[1]);
    while(a*v[1].parte>0&&k>0)
    {
        k--;
        a=arie(v[st[k-1]],v[st[k]],v[1]);
    }
    printf("%d\n",k);
    for(i=1; i<=k; i++)
        cout<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
///printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}