Cod sursa(job #1785569)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 21 octombrie 2016 16:14:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#define NMAX 120005
using namespace std;

struct punct
{
    double x,y;
};

int N,K;
punct puncte[NMAX];
punct stiva[NMAX];
void citire()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        {
            scanf("%lf%lf",&puncte[i].x,&puncte[i].y);
            if(puncte[1].x > puncte[i].x)
                swap(puncte[1],puncte[i]);
            else if(puncte[1].x == puncte[i].x && puncte[1].y > puncte[i].y)
                swap(puncte[1],puncte[i]);
        }
}

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

bool comp(punct a,punct b)
{
    return cross_product(puncte[1],a,b)>0;
}


void infasuratoare()
{
    stiva[++K] = puncte[1];
    stiva[++K] = puncte[2];
    for(int i=3;i<=N;i++)
    {
        while(K>=2 && cross_product(stiva[K-1],stiva[K],puncte[i])<0)
            K--;
        stiva[++K] = puncte[i];
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sort(puncte+2,puncte+N+1,comp);
    infasuratoare();
    printf("%d\n",K);
    for(int i=1;i<=K;i++)
        printf("%lf %lf\n",stiva[i].x,stiva[i].y);

    return 0;
}