Cod sursa(job #2781957)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 octombrie 2021 10:16:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

typedef long double ld;

struct punkt
{
        ld x, y;
} low;

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

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

ld f(punkt a, punkt b, punkt c)
{
        return f(a, b)+f(b, c)+f(c, a);
}

bool cmp(punkt a, punkt b)
{
        return f(low, a, b)>0;
}

const int N=120000+7;
int n;
punkt a[N];
vector<punkt> stk;

void add(punkt a)
{
        while ((int) stk.size()>=2 && f(stk[(int) stk.size()-2], stk[(int) stk.size()-1], a)<=0)
                stk.pop_back();
        stk.push_back(a);
}

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;
        }

        for (int i=2; i<=n; i++)
                if (a[i]<a[1])
                        swap(a[i], a[1]);


        low=a[1];
        sort(a+2, a+n+1, cmp);

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


        add(a[1]);
        stk.pop_back();

        cout<<(int) stk.size()<<"\n";

        for (auto &it : stk)
        {
                cout<<fixed<<setprecision(12)<<it.x<<" "<<it.y<<"\n";
        }

        return 0;
}