Cod sursa(job #3289507)

Utilizator altomMirel Fanel altom Data 27 martie 2025 11:07:23
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n, i, poz;
pair<double, double> v[120005], aux;
vector<pair<double, double>> st;

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c){
    return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}

bool cmp(pair<double, double> a, pair<double, double> b){
    int d=det({0, 0}, a, b);
    if(d!=0){
        return d>0;
    }else{
        return a.first*a.first+a.second*a.second<b.first*b.first+b.second*b.second;
    }
}


int main()
{
    fin>>n;

    for(i=1;i<=n;i++){
        fin>>v[i].first>>v[i].second;
    }

    v[0].first=1005, v[0].second=1005, poz=0;
    for(i=1;i<=n;i++){
        if(v[i].second<v[poz].second || (v[i].second==v[poz].second && v[i].first<v[poz].first)){
            poz=i;
        }
    }

    /*aux=v[1];
    v[1]=v[poz];
    v[poz]=aux;*/
    swap(v[1], v[poz]);
    v[0]=v[1];

    /*for(i=1;i<=n;i++){
        cout<<v[i].first<<" "<<v[i].second<<'\n';
    }
    cout<<'\n';*/

    for(i=1;i<=n;i++){
        v[i].first-=v[0].first;
        v[i].second-=v[0].second;
    }

    /*for(i=1;i<=n;i++){
        cout<<v[i].first<<" "<<v[i].second<<'\n';
    }
    cout<<'\n';*/

    sort(v+2, v+n+1, cmp);


    /*for(i=1;i<=n;i++){
        cout<<v[i].first<<" "<<v[i].second<<'\n';
    }*/


    st.push_back(v[1]), st.push_back(v[2]);
    for(i=3;i<=n;i++){
        //cout<<v[i].first<<" "<<v[i].second<<'\n';
        while(true){
            if(st.size()>=2 && det(st[st.size()-2], st[st.size()-1], v[i])<=0){
            //if(det(st[st.size()-2], st[st.size()-1], v[i])<0 && st.size()>2){
                st.pop_back();
            }else{
                break;
            }
        }
        st.push_back(v[i]);
    }

    fout<<st.size()<<'\n';
    fout<<setprecision(6)<<fixed;
    for(i=0;i<st.size();i++){
        fout<<st[i].first+v[0].first<<" "<<st[i].second+v[0].second<<'\n';
    }



    return 0;
}