Cod sursa(job #3124085)

Utilizator puica2018Puica Andrei puica2018 Data 26 aprilie 2023 20:48:06
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;

struct Point
{
    double x,y;
};

Point a[120005];

long double Dist(Point A,Point B)
{
    return abs(A.x-B.x)+abs(A.y-B.y);
}

int type(Point A,Point B)
{
    if(A.x>B.x)
        swap(A,B);
    if(A.y>B.y)
        return -1;
    return 1;
}

bool f(Point A,Point B,Point C)
{
    if(type(A,B)==-1)
    {
        if(A.y<=B.y)
        {
            if(C.x<B.x)
                return 1;
            return (Dist(C,{B.x,A.y})<Dist(C,{A.x,B.y}));
        }
        if(C.x>B.x)
            return 1;
        return (Dist(C,{B.x,A.y})<Dist(C,{A.x,B.y}));
    }
    if(A.y<=B.y)
    {
        if(C.x<A.x)
            return 1;
        return (Dist(C,{B.x,A.y})>Dist(C,{A.x,B.y}));
    }
    if(C.x>A.x)
        return 1;
    return (Dist(C,{B.x,A.y})>Dist(C,{A.x,B.y}));
}

int ord[120005];

bool cmp(int i,int j)
{
    if(a[i].y!=a[j].y)
        return (a[i].y<a[j].y);
    return (a[i].x>a[j].x);
}

int sz;
int stk[120005];
int viz[120005];

int k;
Point ans[120005];

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>a[i].x>>a[i].y;

    fout<<fixed<<setprecision(12);

    for(int i=1; i<=n; i++)
        ord[i]=i;
    sort(ord+1,ord+n+1,cmp);

    stk[++sz]=ord[1];
    viz[ord[1]]=1;
    stk[++sz]=ord[2];
    viz[ord[2]]=1;

    for(int i=3; i<=n; i++)
    {
        int j=ord[i];
        while(sz>=2 && f(a[stk[sz-1]],a[j],a[stk[sz]])==1)
        {
            viz[stk[sz]]=0;
            sz--;
        }
        stk[++sz]=j;
        viz[j]=1;
    }

    for(int i=1; i<=sz; i++)
        ans[++k]=a[stk[i]];

    sz=0;
    stk[++sz]=ord[n];
    stk[++sz]=ord[n-1];
    for(int i=n-2; i>=1; i--)
    {
        int j=ord[i];
        if(viz[j]==0)
        {
            while(sz>=2 && f(a[stk[sz-1]],a[j],a[stk[sz]])==1)
            {
                viz[stk[sz]]=0;
                sz--;
            }
            stk[++sz]=j;
            viz[j]=1;
        }
    }

    for(int i=2; i<=sz; i++)
        ans[++k]=a[stk[i]];

    fout<<k<<"\n";
    for(int i=1; i<=k; i++)
        fout<<ans[i].x<<" "<<ans[i].y<<"\n";
    return 0;
}