Cod sursa(job #2630206)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 24 iunie 2020 17:36:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pct
{
    long double x, y;
    pct(long double x, long double y)
    {
        this->x=x;
        this->y=y;
    }
    pct(){}
    bool operator<(pct b) const
    {
        if(x==b.x)
            return x<b.x;
        return y<b.y;
    }
    bool operator==(pct b)
    {
        return (x==b.x && y==b.y);
    }
};
long double prod(pct a, pct b, pct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int n,i;
pct mini;
pct a[120005];
vector <pct> v,con;
bool comp(pct a, pct b)
{
    return prod(pct(0, 0), mini, a) <= prod(pct(0,0), mini, b);
}
void add(pct x)
{
    while(con.size()>=2)
    {
        if(prod(con[con.size()-2], con.back(), x)<=0)
            con.pop_back();
        else
            break;
    }
    con.push_back(x);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;

    mini=pct(1e9, 1e9);
    for(i=1;i<=n;i++)
        mini=min(mini, a[i]);

    con.push_back(mini);
    for(i=1;i<=n;i++)
    {
        if(a[i]==mini)
            continue;

        v.push_back(a[i]);
    }

    sort(v.begin(), v.end(), comp);
    for(pct it : v)
        add(it);

    fout<<con.size()<<'\n';
    for(pct it : con)
        fout<<it.x<<' '<<it.y<<'\n';

    return 0;
}