Cod sursa(job #2590700)

Utilizator bogdan2604Bogdan Dumitrescu bogdan2604 Data 28 martie 2020 18:26:38
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,m,i,mn = 1000000001,poz,sz;
double x,y;
pair <double,double> p0;
vector < pair<double,double> > v,stk;

double orientation(pair<double,double> p0, pair<double,double> a, pair<double,double> b)
{
    double orn = (a.second - p0.second) * (b.first - a.first) -
              (b.second - a.second) * (a.first - p0.first);
    if(!orn)
        return 0;
    return (orn > 1 ? 1 : -1);
}
double dist(pair<double,double> a)
{
    return (a.first - p0.first) * (a.first - p0.first) +
           (a.second - p0.second) * (a.second - p0.second);
}
bool cmp(pair<double,double> a, pair<double,double> b)
{
    double orn = orientation(p0,a,b);
    if(!orn)
        return dist(a) < dist(b);
    return orn < 0;
}
int main()
{
    f >> n;
    for(i = 0 ; i < n; ++ i)
    {
        f >> x >> y;
        v.push_back({x,y});
        if(y < mn)
        {
            mn = y;
            poz = i;
        }
        if(y == mn && x < v[poz].first)
            poz = i;
    }
    p0 = v[poz];
    v.erase(v.begin() + poz);
    -- n;
    sort(v.begin(), v.end(), cmp);
    for (i = 0; i < n; ++ i)
    {
        while (i < n-1 && orientation(p0, v[i],
                                      v[i+1]) == 0)
            i++;


        v[m] = v[i];
        ++ m;
    }
    stk.push_back(p0);
    stk.push_back(v[0]);
    stk.push_back(v[1]);
    sz = 3;
    for(i = 2; i < m; ++ i)
    {
        while(orientation(stk[sz - 2],stk[sz - 1],v[i]) == 1)
        {
            stk.pop_back();
            -- sz;
        }
        ++ sz;
        stk.push_back(v[i]);
    }
    g << sz << '\n';
    for(auto &i : stk)
        g << i.first << ' ' << i.second << '\n';
}