Cod sursa(job #1509796)

Utilizator kappykkDragos kappykk Data 24 octombrie 2015 12:24:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#define VM 120005
#define x first
#define y second
#define pdd pair<double,double>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
int vf1, vf2;

pdd p[VM];
pdd stiva1[VM];
pdd stiva2[VM];

bool cmp(pdd a, pdd b){
    if(a.x  != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

double cross_product(pdd o, pdd a, pdd b){
    a.x -= o.x;
    a.y -= o.y;
    b.x -= o.x;
    b.y -= o.y;
    return a.x * b.y - a.y * b.x;
}

int main()
{
    f>>n;
    for(int i = 0 ; i < n ; ++i)
        f>>p[i].x>>p[i].y;
    sort(p , p + n , cmp);

    stiva1[++vf1] = p[0];
    stiva1[++vf1] = p[1];
    for(int i = 2 ; i < n ; ++i){
        while(vf1 >= 2 && cross_product(stiva1[vf1 - 1] , stiva1[vf1] , p[i]) < 0)
            --vf1;
        stiva1[++vf1] = p[i];
    }


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

    g<<vf1 + vf2 - 2<<'\n';
    for(int i = 1 ; i <= vf1 ; ++i)
        g<<fixed<<setprecision(6)<<stiva1[i].x<<' '<<stiva1[i].y<<'\n';
    for(int i = 2 ; i <  vf2 ; ++i)
        g<<fixed<<setprecision(6)<<stiva2[i].x<<' '<<stiva2[i].y<<'\n';

    return 0;
}