Cod sursa(job #2628419)

Utilizator bem.andreiIceman bem.andrei Data 15 iunie 2020 20:52:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("infasuratoare.in");
ofstream w("infasuratoare.out");
struct Point
{
    double x, y;
};
vector<Point>v;
Point g[120005];
int cnt;
double prod(Point a, Point b, Point c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(Point a, Point b)
{
    return prod(g[1], a, b) < 0;
}
int main()
{
    r>>cnt;
    for(int i = 1; i <= cnt; ++i)
    {
        r>>g[i].x>>g[i].y;
    }
    int pos = 1;
    for(int i = 2; i <= cnt; ++i)
    {
        if(g[i].x > g[pos].x)
        {
            continue;
        }
        if(g[i].x < g[pos].x)
        {
            pos = i;
            continue;
        }
        if(g[i].y < g[pos].y)
        {
            pos = i;
        }
    }
    swap(g[1], g[pos]);
    sort(g+2, g+cnt+1, cmp);
    v.push_back(g[1]);
    v.push_back(g[2]);
    for(int i = 3; i <= cnt; ++i)
    {
        while(v.size() >= 2 && prod(v[v.size() - 2], v[v.size() - 1], g[i]) > 0)
        {
            v.pop_back();
        }
        v.push_back(g[i]);
    }
    w<<fixed<<v.size()<<"\n";
    while(!v.empty() )
    {
        w<<setprecision(13)<<v[v.size() - 1].x <<" "<< v[v.size() - 1].y <<"\n";
        v.pop_back();
    }
    return 0;
}