Cod sursa(job #3300649)

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

struct Punct {
    int 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;
    }
};

int 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();


    fout<<infasuratoare.size()<<"\n";
    for (const auto& p : infasuratoare) {
        fout<<p.x<<" "<<p.y<<"\n";
    }

    return 0;
}