Cod sursa(job #2630219)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 24 iunie 2020 18:41:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 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(){}
};
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,minpoz;
pct a[120005];
vector <pct> v,con;
bool comp(pct x, pct y)
{
    return (x.y-a[minpoz].y)*(y.x-a[minpoz].x) < (y.y-a[minpoz].y)*(x.x-a[minpoz].x);
}
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;

    minpoz=1;
    for(i=2;i<=n;i++)
    {
        if(a[i].x==a[minpoz].x && a[i].y<a[minpoz].y)
            minpoz=i;
        if(a[i].x<a[minpoz].x)
            minpoz=i;
    }

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

        v.push_back(a[i]);
    }

    sort(v.begin(), v.end(), comp);

    for(pct it : v)
        add(it);

    fout.precision(12);
    fout<<fixed;

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

    return 0;
}