Cod sursa(job #1887764)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 21 februarie 2017 19:13:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <cstdio>
#include <stack>
#define NMAX 1000005

using namespace std;

int n, pozMin=1;
struct puncte
{
    double x, y;
}v[120005], minim;
stack <double> s;

void read()
{
    scanf("%d", &n);
    minim.x=NMAX;
    minim.y=NMAX;
    for(int i=1; i<=n; ++i)
        {
            scanf("%lf %lf", &v[i].x, &v[i].y);
            if(v[i].x < v[pozMin].x || (v[i].x==v[pozMin].x && v[i].y < v[pozMin].y))
                {
                    swap(v[i], v[pozMin]);
                    pozMin=i;
                }
        }
}

double calcDet(int a, int b, int c)
{
    return (double) v[b].x*v[c].y + v[c].x*v[a].y + v[a].x*v[b].y - v[b].x*v[a].y - v[c].x*v[b].y - v[a].x*v[c].y;
}

void sortarePuncte()
{
    for(int i=2; i<n; ++i)
        for(int j=i+1; j<=n; ++j)
        {
            if(calcDet(1, i, j)<0)
                swap(v[i], v[j]);
        }
}

void solve()
{
    sortarePuncte();
    int k=0, ant1, ant2;
    s.push(1);
    ant2=s.top();
    s.push(2);
    ant1=s.top();
    for(int i=3; i<=n; ++i)
        {
            while(calcDet(ant2, ant1, i)<0)
            {
                s.pop();
                ant1=s.top();
                s.pop();
                ant2=s.top();
                s.push(ant1);
            }
            s.push(i);
            swap(ant1, ant2);
            ant1=i;
        }
    printf("%d\n", s.size());
    while(!s.empty())
    {
        printf("%.2lf %.2lf\n", v[s.top()].x, v[s.top()].y);
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    //freopen("infasuratoare.out", "w", stdout);
    read();
    solve();
    return 0;
}