Cod sursa(job #1879990)

Utilizator Bot32King Max Bot32 Data 15 februarie 2017 12:21:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 120001
#define point pair < double , double >
#define x first
#define y second

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

int n, i , index;
vector < point > v;
point mx;
vector < point > st;

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

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


int main()
{
    f >> n;
    v = vector < point > (n+1);
    f >> v[1].x >> v[1].second;
    mx = v[1];
    for ( i = 2; i <= n ; i++ )
    {
        f >> v[i].x >> v[i].second;
        if ( mx.x > v[i].x or ( mx.x == v[i].x and mx.y > v[i].y) )
        {
            mx = v[i];
            index = i;
        }
    }
    swap(v[1],v[index]);
    sort(v.begin()+2,v.end(),cmp);

    st = vector < point > (n+1);

    st[1] = v[1];
    st[2] = v[2];
    int varf = 2;

    for ( i = 3; i <= n ; i++ )
    {
        while ( varf >= 2 and (det(v[i],st[varf-1],st[varf]) > 0) ) varf--;
        st[++varf] = v[i];
    }
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",varf);
    while ( varf )
    {
        printf("%.12f %.12f\n" ,st[varf].x , st[varf].y);
        varf--;
    }


    return 0;
}