Cod sursa(job #3216154)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 15 martie 2024 17:54:13
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct Punct {long double x , y;}a[120001] , st[120001];
int N , vf;

long double Det (Punct A , Punct B , Punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

long double Dist (Punct A , Punct B)
{
    long double a = A.x - B.x , b = A.y - B.y;
    return a * a + b * b;
}

bool fCmp (Punct A , Punct B)
{
    long double d = Det ({0 , 0} , A , B);
    if(d != 0)
        return d > 0;
    return Dist (A , {0 , 0}) > Dist (B , {0 , 0});
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> a[i].x >> a[i].y;
    int p = 1;
    for (int i = 2; i <= N; ++i)
        if(a[p].y > a[i].y || (a[p].y == a[i].y && a[i].x < a[p].x))
            p = i;
    swap(a[1] , a[p]);
    /// Sortez
    sort (a + 2 , a + N + 1 , fCmp);
    /// Determin punctele coliniare cu originea si cu a[2]
//    int poz = 3;
//    while(poz <= N && Det (a[1] , a[2] , a[poz]) == 0)
//        ++poz;
//    --poz;
    /// Simetrizez secventa
//    for(int i = 2 , j = poz; i < j; ++i , --j)
//        swap(a[i] , a[j]);
    /// Realiz. infasuratoarea
    st[++vf] = a[1] , st[++vf] = a[2];
    for (int i = 3; i <= N; ++i)
    {
        while(vf >= 2 && Det (st[vf - 1] , st[vf] , a[i]) < 0)
            --vf;
        st[++vf] = a[i];
    }
    /// Afisez infas.
    fout << vf << "\n";
    fout << fixed << setprecision(12);
    for (int i = 1; i <= vf; ++i)
        fout << st[i].x  << " " << st[i].y  << "\n";
}