Cod sursa(job #3310956)

Utilizator Mihai_0020Mihai Hoara Mihai_0020 Data 18 septembrie 2025 12:16:26
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura{
    double x,y;
};
bool comp(ura m1, ura m2){
    if(m1.x!=m2.x)
        return m1.x < m2.x;
    return m1.y<m2.y;
}
double miau(ura a1, ura a2, ura a3){
    return (a2.x-a1.x)*(a3.y-a1.y)-(a2.y-a1.y)*(a3.x-a1.x);
}
ura a[120001];
vector <int> infasjos;
vector <int> infassus;
vector <int> infas;
int main()
{
    int n,i,p;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a,a+n,comp);
    for(i=0;i<n;i++){
        while(infasjos.size()>=2&&miau(a[infasjos[infasjos.size()-2]],a[infasjos.back()],a[i])<0)
            infasjos.pop_back();
        infasjos.push_back(i);
    }
    for(i=n-1;i>=0;i--){
        while(infassus.size()>=2&&miau(a[infassus[infassus.size()-2]],a[infassus.back()],a[i])<0)
            infassus.pop_back();
        infassus.push_back(i);
    }
    infasjos.pop_back();
    infassus.pop_back();
    infas=infasjos;
    infas.insert(infas.end(),infassus.begin(),infassus.end());
    cout<<infas.size()<<endl;
    for(i=0;i<infas.size();i++)
        cout<<a[infas[i]].x<<" "<<a[infas[i]].y<<endl;
    return 0;
}