Cod sursa(job #1966906)

Utilizator ana-maria.simiAna-Maria Simionescu ana-maria.simi Data 15 aprilie 2017 17:42:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct { double x,y;} P[120005],st[120005];
int n,vf,i,poz;
double prod(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp(punct A, punct B)
{
    return prod(P[1],A,B)<0;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        scanf("%lf%lf", &P[i].x, &P[i].y);
     poz=1;
    for(i=2; i<=n; i++)
        if(P[poz].y>P[i].y || (P[poz].y==P[i].y && P[poz].x>P[i].x))
            poz=i;
    swap(P[1],P[poz]);
    sort(P+2,P+n+1,cmp);
    st[1]=P[1];
    st[2]=P[2];
    vf=2;
    for(i=3; i<=n; i++)
    {
        while(vf>=2 && prod(st[vf-1],st[vf],P[i])>0)
            vf--;
        st[++vf]=P[i];
    }
    printf("%d\n", vf);
    for(i=vf; i>=1; i--)
        printf("%lf %lf\n", st[i].x, st[i].y);

    return 0;
}