Cod sursa(job #1097967)

Utilizator cristitamasTamas Cristian cristitamas Data 4 februarie 2014 11:56:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;

typedef pair<double,double> punct;

punct Stiva[120001];
punct Sir[120001];
int N,k;

double Rotatie(const punct &A, const punct &B, const punct &C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

bool Cmp(const punct &A, const punct &B)
{
    return Rotatie(Sir[1],A,B)<0;
}

void Citire()
{
    int Poz=1;
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
    {
        scanf("%lf %lf",&Sir[i].x,&Sir[i].y);
        if(Sir[i]<Sir[Poz])
            Poz=i;
    }
    swap(Sir[1],Sir[Poz]);

}

void Infasuratoare()
{
    Stiva[1]=Sir[1];
    Stiva[2]=Sir[2];
    k=2;
    for(int i=3;i<=N;++i)
    {
        while(k>=2 && Rotatie(Stiva[k-1],Stiva[k],Sir[i])>0)
            k--;
        Stiva[++k]=Sir[i];
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    Citire();
    sort(Sir+2,Sir+1+N,Cmp);
    Infasuratoare();
    printf("%d\n",k);
    for(int i=k;i>=0;--i)
        printf("%lf %lf\n",Stiva[i].x,Stiva[i].y);
    return 0;
}