Cod sursa(job #1838622)

Utilizator silkMarin Dragos silk Data 1 ianuarie 2017 15:18:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <algorithm>
#define NMax 120000
#define x first
#define y second
using namespace std;

typedef pair<double, double> Punct;
Punct stiva[NMax+1];
Punct v[NMax+1];
int vf,N;

double ceas_trig(Punct O, Punct A, Punct B)
{
    return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}

bool cmp(const Punct A, const Punct B)
{
    return ( ceas_trig(v[1],A,B) > 0 );
}

void Read()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i) scanf("%lf %lf", &v[i].x, &v[i].y);
}

void Write()
{
    printf("%d\n",vf);
    for(int i = 1; i <= vf; ++i) printf("%lf %lf\n", stiva[i].x, stiva[i].y);
}

void Solve()
{
    int i,pos=1;

    for(i = 2; i <= N; ++i)
    if( v[pos] > v[i] ) pos = i;
    swap(v[1], v[pos]);
    sort(v+2,v+N+1,cmp);

    vf = 2;
    stiva[1] = v[1];
    stiva[2] = v[2];
    for(i = 3; i <= N; ++i)
    {
        while( vf >= 2 && ceas_trig(stiva[vf-1], stiva[vf], v[i]) < 0 ) --vf;
        stiva[++vf] = v[i];
    }
}

int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    Read();
    Solve();
    Write();


return 0;
}