Cod sursa(job #3226700)

Utilizator Luca07Nicolae Luca Luca07 Data 22 aprilie 2024 16:55:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stack>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

vector<pair<double,double>> vp;

double getCProduct(pair<double,double> v1,pair<double,double> v2){
    return v1.first*v2.second-v1.second*v2.first;
}

pair<double,double> makeVector(pair<double,double> p1,pair<double,double> p2){ return {p2.first-p1.first,p2.second-p1.second};}

pair<double,double> po={INT32_MAX,INT32_MAX};

bool isConvex(pair<double,double> p1,pair<double,double> p2){
    return getCProduct(makeVector(po,p1),makeVector(p1,p2))>0;
}

bool compare(pair<double,double> p1,pair<double,double> p2){
    if(isConvex(p1,p2)){
        return true;
    }
    else if(isConvex(p2,p1)){
        return false;
    }else {
        return (abs(p1.first-po.first)+abs(p1.second-po.second))<(abs(p2.first-po.first)+abs(p2.second-po.second));
    }
}

stack<pair<double,double>> sp;

int main()
{
    int i,j,nr,n,id;
    double x,y;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x>>y;
        vp.push_back({x,y});
        if(po>vp[i]){
            po=vp[i];
            id=i;
        }
    }

    vp.erase(vp.begin()+id);
    sort(vp.begin(),vp.end(),compare);

    sp.push(po);
    sp.push(vp[0]);
    for(i=1;i<vp.size();i++){
        pair<double,double> p1=sp.top();
        sp.pop();
        po=sp.top();
        if(isConvex(p1,vp[i])){
            sp.push(p1);
            sp.push(vp[i]);
        }
        else{
            if(sp.size()<2){
                sp.push(p1);
            }
            sp.push(vp[i]);
        }
    }

    cout<<sp.size()<<"\n";
    while(!sp.empty()){
        auto p=sp.top();
        sp.pop();
        cout<<p.first<<" "<<p.second<<"\n";
    }

    return 0;
}