Cod sursa(job #1607315)

Utilizator Bot32King Max Bot32 Data 20 februarie 2016 23:26:25
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cstdio>
using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define point pair < double , double >

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

vector < point > v;
point st[120001];
int n , top ;
float xx , yy;

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

bool comp ( const point &a , const point &b )
{
    return ecuatia_dreptei(v[0],a,b)<0;
}

void citire_date()
{
    f >> n ;
    for ( ; n-- ; )
    {
        f >> xx >> yy;
        v.pb(mp(xx,yy));
    }
    n = v.size();
}

void sortare_puncte()
{
    int poz = 0;
    for ( int i = 1; i < n ; i++ )
        if ( v[i].first < v[poz].first )
            poz = i;
        else if ( v[i].first == v[poz].first and v[i].second < v[poz].second)
            poz = i;

    swap(v[0],v[poz]);
    sort(v.begin()+1 , v.end() , comp );
}

void afis ( )
{
    freopen("infasuratoare.out","w",stdout);
    sort(st+1 , st+top+1 , comp) ;
    printf("%d\n",top);
    for ( int i = top ; i >= 1; i-- )
        printf("%.9f %.9f\n",st[i].x,st[i].y);
}

void infasuratoare_convexa()
{
    sortare_puncte();
    for ( int i = 0 ; i < n ; i++ )
    {
        while ( top >= 2 and ecuatia_dreptei( st[top-1],st[top],v[i] ) > 0 ) top--;
        st[++top] = v[i];
    }
    afis();
}

int main()
{
    citire_date();
    infasuratoare_convexa();
    return 0;
}