Cod sursa(job #3349170)

Utilizator Lex._.Lex Guiman Lex._. Data 25 martie 2026 19:31:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define NMAX 120000
#define x first
#define y second
using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

pair<double, double> v[NMAX+1];

bool clockwise(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    double area=(b.x-a.x)*(a.y+b.y)+(c.x-b.x)*(b.y+c.y)+(a.x-c.x)*(c.y+a.y);
    return area>0;
}

int main()
{
    int n;
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v+1, v+n+1);
    vector<pair<double, double>> up, down;
    pair<double, double> a=v[1], b=v[n];
    up.push_back(a);
    down.push_back(a);
    for(int i=2; i<=n; i++)
    {
        if(i==n || clockwise(a, v[i], b))
        {
            while(up.size()>=2 && !clockwise(up[up.size()-2], up[up.size()-1], v[i]))
                up.pop_back();
            up.push_back(v[i]);
        }
        if(i==n || !clockwise(a, v[i], b))
        {
            while(down.size()>=2 && clockwise(down[down.size()-2], down[down.size()-1], v[i]))
                down.pop_back();
            down.push_back(v[i]);
        }
    }
    out << up.size()+down.size()-2 << "\n";

    for(int i=up.size()-1; i>0; i--)
        out << fixed << setprecision(6) << up[i].x << " " << up[i].y << "\n";

    for(int i=0; i<down.size()-1; i++)
        out << fixed << setprecision(6) << down[i].x << " " << down[i].y << "\n";

    return 0;
}