Cod sursa(job #1394253)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 20 martie 2015 10:05:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct str
{
       double x;
       double y;
       double n1;
       double n2;
}a[120001];
double comp(str a,str b)
{
    return (a.n1*b.n2) < (b.n1*a.n2);
}
double calcarie(double x1,double y1,double x2,double y2,double x3,double y3)
{
       double arie=double((double)x1*(y2-y3)+(double)x2*(y3-y1)+(double)x3*(y1-y2));
       arie=(double)arie/2;
       return arie;
}
int stack[120001];
int pint;
int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    double minx=1000000001,miny=1000000001;
    int indice;
    for(int i=1;i<=n;i++)
    {
            scanf("%lf%lf",&a[i].x,&a[i].y);
            if(minx>a[i].x)
            {
                           minx=a[i].x;
                           miny=a[i].y;
                           indice=i;
            }
            else if(minx==a[i].x&&miny>a[i].y)
            {
                 miny=a[i].y;
                 indice=i;
            }
    }
    for(int i=1;i<indice;i++)
    {
            a[i].n1=a[i].y-a[indice].y;
            a[i].n2=a[i].x-a[indice].x;
    }
    for(int i=indice+1;i<=n;i++)
    {
            a[i].n1=a[i].y-a[indice].y;
            a[i].n2=a[i].x-a[indice].x;
    }
    swap(a[1],a[indice]);
    sort(a+2,a+n+1,comp);
    stack[1]=1;
    stack[2]=2;
    pint=3;
    for(int i=3;i<=n;i++)
    {
            while(calcarie(a[stack[pint-2]].x,a[stack[pint-2]].y,a[stack[pint-1]].x,a[stack[pint-1]].y,a[i].x,a[i].y)<0) pint--;
            stack[pint]=i;
            pint++;
    }
    printf("%d\n",pint-1);
    for(int i=1;i<pint;i++)
    {
            printf("%lf %lf\n",a[stack[i]].x,a[stack[i]].y);
    }
}