Cod sursa(job #3207018)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 24 februarie 2024 18:53:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double maximu = 1e9 + 55;
ll  m;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct el
{
    double x, y;
};
double dist(el a, el b)
{
    return (a. x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double orientation(el a, el b, el c)
{
    return (b. x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool compara(el a, el b)
{
    ll p = orientation({0, 0}, a, b);
    return p > 0;
}
void convexhull(el points[], int n)
{
    double xmin = maximu, ymin = maximu;
    for(int i = 0; i < n; ++i)
    {
        if(points[i].y < ymin)
        {
            xmin = points[i].x, ymin = points[i].y;
        }
        else
        {
            if(points[i].y == ymin && points[i].x < xmin)
            {
                xmin = points[i].x;
            }
        }
    }
    for(int i = 0; i < n; ++i)
    {
        points[i].x -= xmin;
        points[i].y -= ymin;
        if(points[i].x == 0 && points[i].y == 0)
        {
            swap(points[i], points[0]);
        }
    }
    sort(points + 1, points + n, compara);
    el stiva[120005] =  {0};
    stiva[0].x = points[0].x;
    stiva[0].y = points[0].y;
    stiva[1].x = points[1].x;
    stiva[1].y = points[1].y;
    m = 2; // presupunem ca avem minim 2 puncte in  hull mai corect ar fi fost sa fac cu 3
    ll dim = 2;
    for(int i = 2; i < n; ++i)
    {
        while(orientation(stiva[dim - 2], stiva[dim - 1], points[i]) < 0)
        {
            dim--;
        }
        stiva[dim].x = points[i].x;
        stiva[dim].y = points[i].y;
        dim++;
    }
     // actualizam noua dimensiune la hull
     m = dim;
     fout << m << '\n';
     for(int i = 0; i < m; ++i)
     {
         stiva[i].x += xmin;
         stiva[i].y += ymin;
         fout << fixed << setprecision(6) << (double)stiva[i].x << " ";
         fout << fixed << setprecision(6) << (double)stiva[i].y << '\n';
     }

}
el v[120005];
ll n;
int32_t main(int argc, char * argv[])
{
    fin >> n;
    for(int  i= 0; i < n; ++i)
    {
        fin >> v[i].x >> v[i].y;
    }
    convexhull(v, n);
    return 0;
}