Cod sursa(job #1506075)

Utilizator DoraBenzoVelicu Teodora DoraBenzo Data 19 octombrie 2015 23:17:14
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define nmax 120001
using namespace std;

int n;
pair <double, double> v[nmax];
vector <int> p;

void citire()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d", &n);

    for (int i=1;i<=n;++i)
        scanf("%lf%lf",&v[i].first,&v[i].second);
}

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}

struct cmp
{
    bool operator()(pair<double, double> a, pair<double, double> b)
    {
        return det(v[1], a, b) > 0;
    }
};

void infasuratoare()
{
    int poz = 1;
    for(int i = 2; i <= n; i++)
        if(v[1] > v[poz])
            poz = i;

    swap(v[1], v[poz]);
    sort(v+2,v+n+1, cmp());
    for(int i = 1; i <= n; ++i) {
        while(p.size() >= 2 && det(v[p[p.size()-2]],v[p[p.size()-1]],v[i]) < 0)
            p.pop_back();
        p.push_back(i);
    }

    printf("%d\n", p.size ());
    for (int i=0; i<p.size(); ++i)
    printf("%lf %lf\n", v[p[i]].first, v[p[i]].second);
}

int main()
{
    citire();
    infasuratoare();
    return 0;
}