Cod sursa(job #3338167)

Utilizator parrot279Sofi Tudose parrot279 Data 1 februarie 2026 10:38:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int nmax = 12e4+5;

struct pct
{
    double x, y;
};
double arie(pct a, pct b, pct c);
bool cmp(pct a, pct b);
pct v[nmax];

int n, cntsus, cntjos;
vector<pct> sus, jos;

int main()
{
    fin>>n;
    for(int i = 1; i <= n; ++i)
        fin>>v[i].x>>v[i].y;

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

    for(int i = 1; i <= n; ++i)
    {
        while(cntsus >= 2 && arie(sus[cntsus-2], sus[cntsus-1], v[i]) >= 0)
        {
            --cntsus;
            sus.pop_back();
        }
        while(cntjos >= 2 && arie(jos[cntjos-2], jos[cntjos-1], v[i]) <= 0)
        {
            --cntjos;
            jos.pop_back();
        }
        ++cntsus;
        ++cntjos;
        sus.push_back({v[i].x, v[i].y});
        jos.push_back({v[i].x, v[i].y});
    }
    fout<<cntsus + cntjos - 2<<"\n";

    for(int i = 0; i < cntjos; ++i)
        fout<<jos[i].x<<" "<<jos[i].y<<"\n";
    for(int i = cntsus-2; i >= 1; --i)
        fout<<sus[i].x<<" "<<sus[i].y<<"\n";





    return 0;
}

double arie(pct a, pct b, pct c)
{
    return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}
bool cmp(pct a, pct b)
{
    if(a.x == b.x)
        return (a.y < b.y);
    return (a.x < b.x);
}