Cod sursa(job #800204)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 20 octombrie 2012 21:47:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 120001
#define VMAX 1000000001

using namespace std;

FILE *inFile = fopen ("infasuratoare.in", "r");
FILE *outFile = fopen ("infasuratoare.out", "w");

struct punct
{
    double x;
    double y;
    double p;
} p[NMAX];

vector <punct> C;

int n;

bool cmp(punct a, punct b)
{
    if (a.p < b.p)
        return 1;

    return 0;
}

void read()
{
    int poz;
    int xmin = VMAX;
    int ymin = VMAX;

    fscanf (inFile, "%d\n", &n);

    for (int i = 0; i < n; ++ i)
    {
        fscanf (inFile, "%lf %lf\n", &p[i].x, &p[i].y);

        if (p[i].x < xmin || p[i].x == xmin && p[i].y < ymin)
        {
            poz = i;
            xmin = p[i].x;
            ymin = p[i].y;
        }
    }

    swap (p[poz], p[n - 1]);
    -- n;
}

void panta()
{
    for (int i = 0; i < n; ++ i)
    {
        if (p[i].x != p[n].x)
            p[i].p = (p[i].y - p[n].y) / (p[i].x - p[n].x);
        else
            p[i].p = VMAX;
    }

    sort (p, p + n, cmp);
}

double determinant(punct a, punct b, punct c)
{
    return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y;
}

void infasuratoare()
{
    C.push_back(p[n]);
    C.push_back(p[0]);

    for (int i = 1; i < n; ++ i)
    {
        int m = C.size() - 1;

        if (determinant(C[m - 1], C[m], p[i]) >= 0)
            C.push_back(p[i]);
        else
        {
            while (determinant(C[m - 1], C[m], p[i]) < 0)
            {
                C.pop_back();
                -- m;
            }

            C.push_back(p[i]);
        }
    }
}

void write()
{
    fprintf (outFile, "%d\n", C.size());

    for (unsigned int i = 0; i < C.size(); ++ i)
        fprintf (outFile, "%.6lf %.6lf\n", C[i].x, C[i].y);
}

int main()
{
    read();
    panta();
    infasuratoare();
    write();

    return 0;
}