Cod sursa(job #2462723)

Utilizator dan.blanaruDAN BLANARU dan.blanaru Data 27 septembrie 2019 19:03:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;
int n;
struct p{
double x,y;};
vector<p> v,sol;

#define EPS 1e-12

double cp(p p1, p p2, p p3){
    return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}
double cmp(p p1, p p2){
    return (cp(v[0],p1,p2)>0);
}

void sortare()
{
    int imin=0;
    p pmin =v[0];
    for(int i=0;i<n;i++){
        if(v[i].y < pmin.y)
            imin=i,pmin=v[i];
        else if(v[i].y == pmin.y && v[i].x < pmin.x)
            imin=i,pmin=v[i];
    }

    swap(v[0],v[imin]);

    sort(v.begin()+1,v.end(),cmp);

}

void convexhull(){
    sol.push_back(v[0]);
    sol.push_back(v[1]);
    int ssol = 2;
    for(int i=2;i<n;i++){

        while(ssol>=2 && cp(sol[ssol-2],sol[ssol-1],v[i])<EPS)
        {
            sol.pop_back();
            ssol--;
        }
        sol.push_back(v[i]);
        ssol++;
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    double x,y;
    p pnct;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        pnct.x=x,pnct.y=y;
        v.push_back(pnct);
    }


    sortare();
    convexhull();
    cout<<sol.size()<<"\n"<<setprecision(6)<<fixed;
    for(int i=0;i<sol.size();i++)
        cout<<sol[i].x<< " "<<sol[i].y<<"\n";
}