Cod sursa(job #1618011)

Utilizator julianvladucuVladucu Iuliu Cristian julianvladucu Data 27 februarie 2016 17:36:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<algorithm>

using namespace std;
struct punct{
    double x,y;
    }v[120001],sol[120001];
int n,vf;

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

bool cmp(punct a,punct b)
{
    return panta(v[0],a,b)>0;
}

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