Cod sursa(job #2450330)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 22 august 2019 17:17:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>


using namespace std;

typedef long double ld;
const int N=120000+7;
int n;

struct pt
{
        ld x;
        ld y;
};

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

ld ar(pt a,pt b,pt c)
{
        return tr(a,b)+tr(b,c)+tr(c,a);
}

pt mn(pt a,pt b)
{
        if(a.x<b.x)
                return a;
        if(b.x<a.x)
                return b;
        if(a.y<b.y)
                return a;
        return b;
}

pt loft;

bool cmp(pt a,pt b)
{
        if(a.x==loft.x && a.y==loft.y) return 1;
        if(b.x==loft.x && b.y==loft.y) return 0;
        return (ar(loft,a,b)>0);
}

pt st[N];
int top;

void baga(pt a)
{
        while(top>=2 && (ar(st[top-1],st[top],a)<=0))
                top--;
        st[++top]=a;
}

pt a[N];

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

        cin>>n;
        for(int i=1;i<=n;i++)
                cin>>a[i].x>>a[i].y;
        loft=a[1];
        for(int i=2;i<=n;i++)
                loft=mn(loft,a[i]);

        sort(a+1,a+n+1,cmp);

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

        return 0;
}