Cod sursa(job #1922430)

Utilizator george_stelianChichirim George george_stelian Data 10 martie 2017 17:27:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct punct
{
    double x,y;
}v[120010],q[120010];

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

int cmp(punct a,punct b)
{
    return det(v[1],a,b)>0;
}

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