Cod sursa(job #2763340)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 13 iulie 2021 11:48:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
int i, n, minn;
int stiva[125005];
int n_stiva;
struct coord
{
    double x, y;
}v[125005];
double cross_product(coord a, coord b, coord c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(coord a, coord b)
{
    double aux = cross_product(v[1], a, b);
    if(aux < 0)return false;
    return true;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f >> n;
    minn = -1;
    for(i = 1; i <= n; i ++)
    {
        f >> v[i].x >> v[i].y;
        if(minn == -1)minn = i;
        else if(v[i].y < v[minn].y)minn = i;
    }
    swap(v[1], v[minn]);
    sort(v + 2, v + n + 1, cmp);
    /*
    for(i = 1; i <= n; i ++)
        g << v[i].x << " " << v[i].y << "\n";
    */
    for(i = 1; i <= n; i ++)
    {
        if(n_stiva < 2)
        {
            n_stiva ++;
            stiva[n_stiva] = i;
            continue;
        }
        while(n_stiva >= 2 && cross_product(v[n_stiva - 1], v[stiva[n_stiva]], v[i]) < 0)
            n_stiva --;
        n_stiva ++;
        stiva[n_stiva] = i;
    }
    g << n_stiva << "\n";
    for(i = 1; i <= n_stiva; i ++)
        g << v[stiva[i]].x << " " << v[stiva[i]].y << "\n";
    return 0;
}