Cod sursa(job #3299507)

Utilizator Mihai00700Mihai Ghetu Mihai00700 Data 7 iunie 2025 14:30:25
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct ura{
    double x, y;
} v[120002], stiva1[120002], stiva2[120002];//doua stive - ok :)

double arie (double xa,double xb,double xc,double ya,double yb,double yc){ //calculam aria
    return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}
bool cmp (ura a, ura b){ //sortam punctele dupa x si la x egal dupa y
    if(a.x < b.x){
        return true;
    }else{
        if(a.x == b.x){
            if(a.y < b.y){
                return true;
            }
            return false;
        }
        return false;
    }
}


int main(){
    int n;
    f>>n;
    for (int i=1; i<=n; i++) //citim punctele
        f>>v[i].x>>v[i].y;
    sort (v+1,v+n+1, cmp); //sortam punctele

    ura st=v[1], dr=v[n]; //initializam punctele care definesc dreapta de diferentiere

    int sp1=1; // inaltimea stivei
    stiva1[1]=st; // initializam stiva 
    for (int i=2; i<=n; i++){
        if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y)<=0) //dedesubt
        {
            while (sp1>1&&arie(stiva1[sp1-1].x, stiva1[sp1].x, v[i].x, stiva1[sp1-1].y, stiva1[sp1].y, v[i].y)<0)
            {
                sp1--;
            }
            sp1++;
            stiva1[sp1]=v[i];
        }
    }
    int h=sp1;

    int sp2=1;
    stiva2[1] = dr;
    for (int i=n-1; i>=1; i--) //deasupra
    {
        if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y)>=0)
        {
            while (sp2>1 && arie(v[i].x, stiva2[sp2].x, stiva2[sp2 -1].x, v[i].y, stiva2[sp2].y, stiva2[sp2 - 1].y) > 0){
                sp2--;
            }
            sp2++;
            stiva2[sp2]=v[i];
        }
    }
    h+=sp2;
    g<<h - 2<<"\n";
    g<<setprecision(6)<<fixed;

    for (int i=2; i<=sp1; i++)
        g<<stiva1[i].x<<" "<<stiva1[i].y<<"\n";
    for (int i=2; i<sp2; i++)
        g<<stiva2[i].x<<" "<<stiva2[i].y<<"\n";
    g<<st.x<<" "<<st.y<<"\n";
    return 0;
}