Cod sursa(job #1590953)

Utilizator danstefanDamian Dan Stefan danstefan Data 5 februarie 2016 17:41:20
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define eps 1e-12
using namespace std;
int n,i,h,k,q;
typedef struct coordonata
{
    double x,y;
};
coordonata p[120010],v[120010];
int s[120010],ok[120010];

inline int cmp1(double a,double b)
{
    if (a+eps<b) return 1;
    if (b+eps<a) return -1;
    return 0;
}

bool cmp(const coordonata &a,const coordonata&b)
{
    int t;
    t=cmp1(a.x,b.x);
    if (t!=0) return t==1;
    return (cmp1(a.y,b.y)==1);
}

int semn(coordonata a,coordonata b,coordonata c)
{
    double A,B,C;
    A = a.y-b.y;
    B = b.x-a.x;
    C = a.x*b.y - b.x*a.y;
    return cmp1(A*c.x+B*c.y+C,0);
}

int main ()
{
    freopen("infasuratoare.in","r",stdin);
    ofstream g ("infasuratoare.out");
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    q=1;
    k=2;
    i=3;
    while (!ok[1])
    {
        while (ok[i])
        {
            if (i==n) q=-1;
            i+=q;
        }
        while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
        {
            ok[s[k--]]=0;
        }
        s[++k]=i;
        ok[i]=1;
    }
    h=k-1;
    g<<h<<'\n';
    for (i=2; i<=h+1; i++)
      g<<setprecision(6)<<fixed<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
    return 0;
}