Cod sursa(job #1293368)

Utilizator akaprosAna Kapros akapros Data 15 decembrie 2014 20:24:46
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,nr;
struct punct
{
    double x;
    double y;
}q,cp,v[120005],w[120005];
double cmp(const punct a,const punct b)
{
    return (a.x-q.x)*(b.y-q.y)>(b.x-q.x)*(a.y-q.y);
}
double sp(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));
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    p=1;
    for (i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        if ((v[i].x<v[p].x)&&(v[i].y<v[p].y)) p=i;
    }
    q=v[p];  punct aux;
    aux=v[p]; v[p]=v[1]; v[1]=aux;
    sort(v+1,v+n+1,cmp);
    nr=2; w[1]=v[1]; w[2]=v[2];
    for (i=3;i<=n;i++)
    {
        while (sp(w[nr-1],w[nr],v[i])<=0) nr--;
        w[++nr]=v[i];
    }
    printf("%d\n",nr);
    for (i=1;i<=nr;i++) printf("%.12lf %.12lf\n",w[i].x,w[i].y);
    return 0;
}