Cod sursa(job #1805930)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 14 noiembrie 2016 17:59:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define x first
#define y second
const int MAX = 120000;

int n;

typedef pair<double, double> puncte;

puncte v[MAX + 1], st[MAX + 1];
int top;

double cross_product(puncte a, puncte b, puncte c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(puncte a, puncte b)
{
    return cross_product(v[1], a, b) < 0;
}

void sort_puncte()
{
    int p = 1;
    for(int i = 2; i <= n; i++)
        if(v[i] < v[p])
            p = i;
    swap(v[1], v[p]);
    sort(v + 2, v + n + 1, cmp);
}

void convex_hull()
{
    sort_puncte();

    st[1] = v[1];
    st[2] = v[2];
    top = 2;
    for(int i = 3; i <= n; i++)
    {
        while(top >= 2 && cross_product(st[top - 1], st[top], v[i]) > 0)
            top--;
        st[++top] = v[i];
    }

}

int main()
{
    FILE *fin, *fout;

    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");

    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n; i++)
        fscanf(fin, "%lf %lf", &v[i].x, &v[i].y);

    convex_hull();

    fprintf(fout, "%d\n", top);
    for(int i = top; i > 0; i--)
        fprintf(fout, "%.9lf %.9lf\n", st[i].x, st[i].y);

    return 0;
}