Cod sursa(job #2428402)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 5 iunie 2019 07:11:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

const int N=120000+7;

struct P
{
        double x;
        double y;
};

int n;
P v[N];

double tr(P a,P b)
{
        return (a.x-b.x)*(a.y+b.y);
}

int ar(P a,P b,P c)
{
        double r=tr(a,b)+tr(b,c)+tr(c,a);
        if(r>0) return +1;
        if(r<0) return -1;
        return 0;
}

P lo;

bool operator == (P a,P b)
{
        return (a.x==b.x && a.y==b.y);
}

bool cmp(P a,P b)
{
        if(a==lo) return 1;
        if(b==lo) return 0;
        return (ar(lo,a,b)>0);
}

bool operator < (P a,P b)
{
        if(a.x!=b.x)
        {
                return a.x<b.x;
        }
        else
        {
                return a.y<b.y;
        }
}

P stk[N];
int top;

void add(P a)
{
        while(top>=2 && ar(stk[top-1],stk[top],a)<=0)
        {
                top--;
        }
        top++;
        stk[top].x=a.x;
        stk[top].y=a.y;
}

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

        cin>>n;
        for(int i=1;i<=n;i++)
        {
                cin>>v[i].x>>v[i].y;
                if(i==1)
                {
                        lo=v[i];
                }
                else
                {
                        lo=min(lo,v[i]);
                }
        }
        sort(v+1,v+n+1,cmp);

        for(int i=1;i<=n;i++)
        {
                add(v[i]);
        }
        add(v[1]);

        top--;
        cout<<top<<"\n";
        for(int i=1;i<=top;i++)
        {
                cout<<fixed<<setprecision(6)<<stk[i].x<<" "<<stk[i].y<<"\n";
        }

        return 0;
}