Cod sursa(job #2193612)

Utilizator ancabdBadiu Anca ancabd Data 10 aprilie 2018 18:30:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

#define INF 1000000001

int n;

struct punct
{
    double x, y, unghi;
    bool operator < (const punct& p) const
	{
		return unghi > p.unghi;
	}
};

vector<punct> A;
vector<int> X;

double CalcCos(int a, int b)
{
    double Cop, Cal, Ip;

    Cop = A[b].y - A[a].y;
    Cal = A[b].x - A[a].x;
    Ip = sqrt(Cop * Cop + Cal * Cal);

    if (Ip)return Cal/Ip;
    else return 1;
}
double CalcUnghi(int a, int b, int c)
{
    return (A[b].y - A[a].y)*(A[c].x - A[b].x) - (A[c].y - A[b].y) * (A[b].x - A[a].x);
}
int main()
{
    fin >> n;

    A = vector<punct>(n + 1);

    int ind;
    double xmin = INF, ymin = INF;
    for (int i = 1; i <= n; i ++)
    {
        fin >> A[i].x >> A[i].y;
        if ((A[i].y < ymin) || (A[i].y == ymin && A[i].x < xmin))
        {
            xmin = A[i].x;
            ymin = A[i].y;
            ind = i;
        }
    }
    for (int i = 1; i <= n; i ++)
        A[i].unghi = CalcCos(ind, i);

    sort(A.begin() + 1, A.end());

    X.push_back(1);
    X.push_back(2);
    X.push_back(3);

    for (int i = 4; i <= n; i ++)
    {
        int sz = X.size();
        while (sz >= 2 && CalcUnghi(X[sz - 2], X[sz - 1], i) > 0)
        {
            X.pop_back();
            sz--;
        }
        X.push_back(i);
    }

    fout << X.size() << '\n';
    for (unsigned int i = 0; i < X.size(); i ++)
        fout << fixed << setprecision(7) << A[X[i]].x << ' ' << A[X[i]].y << '\n';

    return 0;
}