Cod sursa(job #3207013)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 24 februarie 2024 18:27:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
int m, n;
struct el
{
    double x, y;
}v[120005];
double dist(el a, el b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int orientation(el a, el b, el c)
{
    double val = (b.y - a.y) * (c. x - b.x) - (b. x - a.x) * (c. y - b.y);
    if(val == 0) // coliniaritate
    {
        return 0;
    }
    else
    {
        if(val > 0)
        {
            return 1; // inv trigo
        }
        else
        {
            return 2; // trigo
        }
    }
}
el elem;
el stiv(stack<el>&S)
{
    el aux = S.top();
    S.pop();
    el auxi = S.top();
    S.push(aux);
    return auxi;
}
void schimba(el &p1, el &p2)
{
    el auxi = p1;
    p1 = p2;
    p2 = auxi;
}
bool compara(el p1, el p2)
{
    int t = orientation(elem, p1, p2);
    if(t == 0)
    {
        return (dist(elem, p2) >= dist(elem, p1)?-1:1);
    }
    return ((t == 2)?-1:1);
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
void convexhull(el points[], int n)
{
    double ymin = points[1].y;
    int mini = 1;
    for(int i = 2; i <= n; ++i)
    {
        double u = points[i].y;
        if((u < ymin) || (u == ymin && points[i]. x < points[mini].x))
        {
            ymin = u;
            mini = i;
        }
    }
    schimba(points[1], points[mini]);
    elem = points[1];
    sort(points + 2, points + n + 1, compara);
    m = 1;
    for(int i = 2; i <= n; ++i)
    {
        while(i < n && orientation(elem, points[i], points[i + 1]) == 0)
        {
            i++;
        }
        points[m] = points[i];
        m++;
    }
    if(m < 3)
    {
        return;
    }
    stack<el>stiva;
    stiva.push(points[1]);
    stiva.push(points[2]);
    stiva.push(points[3]);
    for(int i = 4; i <= m; ++i)
    {
        while(stiva.size() > 1 && orientation(stiv(stiva), stiva.top(), points[i]) != 2)
        {
            stiva.pop();
        }
        stiva.push(points[i]);
    }
    fout << stiva.size() << '\n';
    while(!stiva.empty())
    {
        fout << fixed << setprecision(6) << (double)stiva.top().x << " ";
        fout << fixed << setprecision(6) << (double)stiva.top().y << '\n';
        stiva.pop();
    }
}
int32_t main(int argc, char * argv[])
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i].x >> v[i].y;
    }
    convexhull(v, n);
    return 0;
}