Cod sursa(job #2146683)

Utilizator zanugMatyas Gergely zanug Data 28 februarie 2018 09:48:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <iomanip>
#include <queue>

#define ld long double

using namespace std;

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

const int NLIM = 12e4 + 10;

struct pont
{
    ld x, y;
};

int n;
pont vp[NLIM];

ld dist2(pont p1, pont p2)
{
    return (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
}

int orientation(pont p1, pont p2, pont p3)
{
    ld val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);

    if(val < 0)
        return -1;///left
    if(val > 0)
        return 1;///right

    return 0;///collinear

}

int compare(const void* a, const void* b)
{
    pont p1 = *(pont*)a;
    pont p2 = *(pont*)b;

    int ori = orientation(vp[0], p1, p2);
    if(!ori)
        return dist2(vp[0], p1) - dist2(vp[0], p2);
    return ori;
}

int main()
{
    int st = 0;

    fin >> n;
    for(int i = 0; i < n; ++i)
    {
        fin >> vp[i].x >> vp[i].y;

        if(vp[i].x < vp[st].x || (vp[i].x == vp[st].x && vp[i].y < vp[st].y))
            st = i;
    }

    pont emp = vp[st];
    vp[st] = vp[0];
    vp[0] = emp;

    qsort(vp + 1, n-1, sizeof(pont), compare);

    queue <int> conv;

    conv.push(0);
    conv.push(1);

    for(int i = 2; i < n; ++i)
    {
        bool b = true;
        while(b)
        {
            b = false;

            int i2 = conv.front();
            conv.pop();
            int i1 = conv.front();

            int ori = orientation(vp[i1], vp[i2], vp[i]);

            if(ori <= 0)
            {
                conv.push(i2);
            }
            else
            {
                b = true;
            }
        }
        conv.push(i);
    }

    fout << conv.size() << "\n";
/*
    stack <int> revconv;
    while(conv.size())
    {
        revconv.push(conv.top());
        conv.pop();
    }
*/
    while(conv.size())
    {
        int cur = conv.front();
        fout << fixed << setprecision(6) << vp[cur].x << " " << vp[cur].y << "\n";
        conv.pop();
    }

    return 0;
}