Cod sursa(job #2842497)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 31 ianuarie 2022 23:11:04
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define cx first
#define cy second

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

int n;
pair <double, double> pct[120005];
vector <int> sus, jos, ans; /// suspisisus

double arie(int a, int b, int c)
{
    /// ax ay 1 )
    /// bx by 1  ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
    /// cx cy 1 )
    return pct[a].cx * pct[b].cy + pct[a].cy * pct[c].cx + pct[b].cx * pct[c].cy - pct[b].cy * pct[c].cx - pct[a].cy * pct[b].cx - pct[a].cx * pct[c].cy;

}

int cadran(int x)
{
    if(pct[x].cx >= 0 && pct[x].cy >= 0)
        return 1;
    if(pct[x].cx < 0 && pct[x].cy >= 0)
        return 2;
    if(pct[x].cx < 0 && pct[x].cy < 0)
        return 3;
    if(pct[x].cx >= 0 && pct[x].cy < 0)
        return 4;
}

bool cmp(int a, int b)
{
    if(cadran(a) == cadran(b))
        return (pct[a].cy / pct[a].cx) < (pct[b].cy / pct[b].cx);
    return cadran(a) < cadran(b);

}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> pct[i].cx >> pct[i].cy;
    sort(pct + 1, pct + n + 1);
    sus.push_back(1);
    jos.push_back(1);
    for(int i = 2; i < n; i++)
    {
        if(arie(sus.back(), i, n) > 0)
            sus.push_back(i);
        if(arie(jos.back(), i, n) < 0)
            jos.push_back(i);
    }
    sus.push_back(n);
    jos.push_back(n);
    fout << sus.size() + jos.size() - 2 << '\n';
    for(int ind : sus)
        ans.push_back(ind);
    for(int ind : jos)
    {
        if(ind != 1 && ind != n)
            ans.push_back(ind);
    }
    sort(ans.begin(), ans.end(), cmp);
    fout << setprecision(12) << fixed;
    for(int ind : ans)
        fout << pct[ind].cx << ' ' << pct[ind].cy << '\n';
    return 0;
}