Cod sursa(job #3300653)

Utilizator alexxsFilca Paul Alexandru alexxs Data 18 iunie 2025 13:26:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Punct {
    double x,y;
    bool operator<(const Punct& alt) const {
        return x<alt.x || (x==alt.x && y<alt.y);
    }

    bool operator==(const Punct&alt)const {
        return x==alt.x && y==alt.y;
    }
};

double orientare(const Punct& a, const Punct& b, const Punct& c) {
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n,i,k;
    fin>>n;
    vector<Punct> puncte(n);
    for(i=0;i<n;i++)
        fin>>puncte[i].x>>puncte[i].y;
    sort(puncte.begin(),puncte.end());
    vector<Punct> infasuratoare;

    for(i=0;i<n;i++) {
        while(infasuratoare.size()>=2 && orientare(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i])<=0)
            infasuratoare.pop_back();
        infasuratoare.push_back(puncte[i]);
    }


    k=infasuratoare.size();
    for(i=n-2;i>=0;i--) {
        while(infasuratoare.size()>k && orientare(infasuratoare[infasuratoare.size()-2],infasuratoare[infasuratoare.size()-1],puncte[i])<=0)
            infasuratoare.pop_back();
        infasuratoare.push_back(puncte[i]);
    }


    if (infasuratoare.size()>1 && infasuratoare.front()==infasuratoare.back())
        infasuratoare.pop_back();

    if (infasuratoare.size() > 1 && infasuratoare.front() == infasuratoare.back())
        infasuratoare.pop_back();


    fout<<infasuratoare.size()<<"\n";
    fout <<fixed <<setprecision(6);
   for (i=0;i<infasuratoare.size();i++) {
    fout << infasuratoare[i].x <<" "<< infasuratoare[i].y<<"\n";
}

    return 0;
}