Cod sursa(job #2716451)

Utilizator BaraianTudorBaraian Tudor Stefan BaraianTudor Data 5 martie 2021 11:05:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <algorithm>
#include <stack>
#define x first
#define y second
#define pb push_back
#define pdd pair<double,double>
#define pii pair<int,int>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pdd sir[120005],t;
bool ok=0;
int n;
stack <pii> s;
double det(pdd a,pdd b,pdd c)
{
    return (a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-c.y*a.x-b.x*a.y);
}
vector<int>v,v1;
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>sir[i].x>>sir[i].y;
    }
    sort(sir+1,sir+n+1);
    s.push({0,1});
    for(int i=2;i<=n;i++)
    {
        while(s.size()>1 && det(sir[s.top().x],sir[s.top().y],sir[i])<0.0)
        {
            s.pop();
        }
        s.push({s.top().y,i});
    }
    while(!s.empty())
    {
        v.pb(s.top().y);
        s.pop();
    }
    s.push({0,1});
    for(int i=2;i<=n;i++)
    {
        while(s.size()>1 && det(sir[s.top().x],sir[s.top().y],sir[i])>0.0)
        {
            s.pop();
        }
        s.push({s.top().y,i});
    }
    s.pop();
    while(s.size()>1)
    {
        v1.pb(s.top().y);
        s.pop();
    }
    out<<v.size()+v1.size()<<'\n';
    out<<fixed<<setprecision(6);
    for(auto i:v)
    {
        out<<sir[i].x<<' '<<sir[i].y<<'\n';
    }
    for(int i=v1.size()-1;i>=0;i--)
    {
        out<<sir[v1[i]].x<<' '<<sir[v1[i]].y<<'\n';
    }
    return 0;
}