Cod sursa(job #3298571)

Utilizator marctudor_ghenceaMarc-Tudor Ghencea marctudor_ghencea Data 31 mai 2025 12:27:27
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int stiva[120001];

struct pct{
 double x, y;
}v[120001];

bool cmp(pct a, pct b){
    if(a.x < b.x)
        return true;
    else
        if(a.x > b.x)
            return false;
        else
            if(a.y < b.y)
                return true;
            return false;
    return false;
}

double arie2(pct a, pct b, pct c){
    return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
}

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

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

    int k = 1;
    stiva[k] = 1;
    for(int i = 2; i < n; i++){
        if(arie2(v[1], v[n], v[i]) > 0){
            while(k > 1 && arie2(v[stiva[k]], v[stiva[k-1]], v[i]) > 0){
                k--;
            }
            stiva[++k] = i;
        }
    }
    stiva[++k] = n;
    int lim = k+1;
    for(int i = 2; i < n; i++){
        if(arie2(v[1], v[n], v[i]) < 0){
            while(k > lim && arie2(v[stiva[k-1]], v[stiva[k]], v[i]) < 0){
                k--;
            }
            stiva[++k] = i;
        }
    }

    cout << k << "\n";
    for(int i = 1; i <= k; i++){
        cout << v[stiva[i]].x << " " << v[stiva[i]].y << "\n";
    }
    return 0;
}