Cod sursa(job #3219303)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 30 martie 2024 17:54:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 12e4;

struct nod{
    long double x, y;
};

long double arie(long double xa, long double ya, long double xb, long double yb, long double xc, long double yc){
    
    return (xa * (yb - yc) + xb * (yc - ya) + xc * (ya - yb));
    
}

bool pozitiv(long double val){
    
    if(val >= 0)
        return true;
    
    return false;
    
}

nod v[NMAX+1];
stack<int> stiva;

long double prelucrat(nod val){
    
    long double xa = val.x;
    long double ya = val.y;
    
    int aux = stiva.top();
    
    stiva.pop();
    
    long double xb = v[aux].x;
    long double yb = v[aux].y;
    
    long double xc = v[stiva.top()].x;
    long double yc = v[stiva.top()].y;
    
    stiva.push(aux);
    
    return arie(xa, ya, xb, yb, xc, yc);
    
}

bool cmp(nod a, nod b){
    
    return a.x < b.x or(a.x == b.x and a.y < b.y);
    
}

int main()
{
    int n;
    f >> n;
    
    
    
    for(int i=1; i<=n; i++)
        f >> v[i].x >> v[i].y;
        
    sort(v+1, v+1+n, cmp);
    
    for(int i=1; i<=n; i++){
        
        while(stiva.size() >= 2 and prelucrat(v[i]) > 0)
            stiva.pop();
            
        stiva.push(i);
        
    }
    
    vector<nod> rez1, rez2;
    
    while(!stiva.empty()){
        
        long double x = v[stiva.top()].x;
        long double y = v[stiva.top()].y;
        
        rez1.push_back({x, y});
        
        stiva.pop();
        
    }
    
    for(int i=1; i<=n; i++){
        
        while(stiva.size() >= 2 and prelucrat(v[i]) < 0)
            stiva.pop();
            
        stiva.push(i);
        
    }
    
    while(!stiva.empty()){
        
        long double x = v[stiva.top()].x;
        long double y = v[stiva.top()].y;
        
        rez2.push_back({x, y});
        
        stiva.pop();
        
    }
    
    g << rez1.size() + rez2.size() - 2;
    
    g << "\n";
    
    reverse(rez1.begin(), rez1.end());
    
    for(int i=0; i<rez1.size()-1; i++){
        g << fixed << setprecision(6) << rez1[i].x << ' ' << rez1[i].y << "\n";
    }
    
    for(int i=0; i<rez2.size()-1; i++){
        g << fixed << setprecision(6) << rez2[i].x << ' ' << rez2[i].y << "\n";
    }
    
    return 0;
}