Cod sursa(job #1644375)

Utilizator george_stelianChichirim George george_stelian Data 9 martie 2016 22:47:09
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;

typedef pair<double,double> punct;
punct v[120010];
int q[120010];

int cmp(punct a,punct b)
{
    return atan2(a.y-v[1].y,a.x-v[1].x)<atan2(b.y-v[1].y,b.x-v[1].x);
}

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 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]<v[1]) swap(v[i],v[1]);
    sort(v+2,v+1+n,cmp);
    q[++nr]=1;
    for(int i=2;i<=n;i++)
    {
        while(nr>=2 && det(v[q[nr-1]],v[q[nr]],v[i])<0) nr--;
        q[++nr]=i;
    }
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++) printf("%f %f\n",v[q[i]].x,v[q[i]].y);
    return 0;
}