Cod sursa(job #2691780)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 29 decembrie 2020 23:29:59
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb

#include <bits/stdc++.h>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const int NMAX = 120000;

pair<double, double> vec[1 + NMAX];

int vf;
int stiva[1 + NMAX];

const double EPS = 0.0000000000001;

inline double ccw(const pair<double, double>& a, const pair<double, double>& b)
{
    return a.first * b.second - a.second * b.first;
}

bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
    //return ccw(a, b) > EPS;
    return atan2(a.second, a.first) < atan2(b.second, b.first);
}

	inline double ccw(const pair<double, double>& o, const pair<double, double>& a, const pair<double, double>& b)
{
    return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;

    double gX = 0.0;
    double gY = 0.0;

    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> vec[i].first >> vec[i].second;

        gX += vec[i].first;
        gY += vec[i].second;
    }

    gX /= (n * 1.0);
    gY /= (n * 1.0);

    //out << gX << ' ' << gY << '\n';

    for (int i = 1; i <= n; i++)
    {
        vec[i].first -= gX;
        vec[i].second -= gY;
    }

    sort(vec + 1, vec + 1 + n, comp);

    /*
    for (int i = 1; i <= n; i++)
    {
        out << vec[i].first + gX << ' ' << vec[i].second + gY << '\n';
    }
    */

    vf++;
    stiva[vf] = 1;
    vec[n + 1].first = vec[1].first;
    vec[n + 1].second = vec[1].second;

    for (int i = 2; i <= n + 1; i++)
    {
        while (vf >= 2 && ccw(vec[stiva[vf - 1]], vec[stiva[vf]], vec[i]) < EPS)
        {
            vf--;
        }
        vf++;
        stiva[vf] = i;
    }

    vf--;
    out << vf << '\n' << fixed << setprecision(6);
    for (int i = 1; i <= vf; i++)
    {
        out << vec[stiva[i]].first + gX << ' ' << vec[stiva[i]].second + gY << '\n';
    }

    return 0;
}