Cod sursa(job #1076652)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 10 ianuarie 2014 14:35:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120000+5
using namespace std;

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

struct punct
{
    double x, y;
    punct(double x = 0, double y = 0): x(x), y(y)
    {

    }
};

double determinant(punct a, punct b, punct c)
{
    double d = a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - c.y * a.x - a.y * b.x;
    //cout << d << '\n';
    return d;
}

bool cmp(punct a, punct b)
{
    return a.y < b.y || a.y == b.y && a.x < b.x;
}

punct plan[nmax];
int stiva[nmax];
int n;
int top;
int u[nmax];

int main()
{
    int i, cnt;
    double det;
    fin >> n;

    for (i = 1; i <= n; i++)
        fin >> plan[i].x >> plan[i].y;

    sort(plan + 1, plan + n + 1, cmp);

    stiva[++top] = 1;
    stiva[++top] = 2;

    u[1] = u[2] = 1;
    for (i = 3; i <= n; i++)
    {
        if (!u[i])
        {
            if (top > 1)
            {
                det = determinant(plan[stiva[top-1]], plan[stiva[top]], plan[i]);
                if (det <= 0)
                {
                    u[stiva[top]] = 0;
                    top--;
                    i--;
                    continue;
                }
            }
            stiva[++top] = i;
            u[i] = 1;
        }
    }

    for (i = n; i >= 2; i--)
    {
        if (!u[i])
        {
            if (top > 1)
            {
                det = determinant(plan[stiva[top-1]], plan[stiva[top]], plan[i]);
                if (det <= 0)
                {
                    u[stiva[top]] = 0;
                    top--;
                    i++;
                    continue;
                }
            }
            stiva[++top] = i;
            u[i] = 1;
        }
    }

    freopen("infasuratoare.out", "w", stdout);
    printf("%d\n", top);
    //fout << top << '\n';
    for (i = 1; i <= top; i++)
    {
        printf("%llf %llf\n", plan[stiva[i]].x, plan[stiva[i]].y);
        //fout <<  setprecision(8) << plan[stiva[i]].x << ' ' << plan[stiva[i]].y << ' ';
        //fout << '\n';
    }
    //fout << '\n';

    return 0;
}