Cod sursa(job #966376)

Utilizator andrettiAndretti Naiden andretti Data 25 iunie 2013 20:00:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define maxn 120005
#define inf 1000000005
using namespace std;

struct point{double x,y;};
point v[maxn];

int n,u;
int minx=inf,miny=inf,p1;
int stack[maxn];

void cit()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(v[i].y<miny || (v[i].y==miny && v[i].x<minx))
        {
            minx=v[i].x;
            miny=v[i].y;
            p1=i;
        }
    }
}

void swap(int i,int j)
{
    point aux;
    aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}

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

double dist(point a,point b)
{
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}

int cmp(point a,point b)
{
    double k=side(v[1],a,b);
    if(k==0) return dist(v[1],a)<dist(v[1],b);
    else return k<0;
}

void sort_by_angle()
{
    swap(1,p1);
    sort(v+2,v+n+1,cmp);
}

void convex_hull()
{
    int i;

    stack[1]=1; stack[2]=2; u=2;
    for(i=3;i<=n;i++)
    {
        while(u>=2 && side(v[stack[u-1]],v[stack[u]],v[i])>0) u--;
        stack[++u]=i;
    }
}

void afis()
{
    int i;
    printf("%d\n",u);

    for(i=1;i<=u;i++)
     printf("%.6lf %.6lf\n",v[stack[i]].x,v[stack[i]].y);
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    cit();
    sort_by_angle();
    convex_hull();
    afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}