Cod sursa(job #1334478)

Utilizator vlady1997Vlad Bucur vlady1997 Data 4 februarie 2015 13:56:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
        #include <cstdio>
        #include <algorithm>
        using namespace std;
        struct infasuratoare
        {
            double x, y;
        };
        infasuratoare a[120001];
        int q[120001], nr=0;
        bool sel[120001];
        bool cmp (infasuratoare c, infasuratoare d)
        {
            if (c.y==d.y) return c.x<d.x;
            else return c.y<d.y;
        }
        int semn (infasuratoare X, infasuratoare Y, infasuratoare Z)
        {
            double a=X.y-Y.y;
            double b=Y.x-X.x;
            double c=Y.y*X.x-Y.x*X.y;
            if (a*Z.x+b*Z.y+c>=0) return 1;
            else return -1;
        }
        void solve (int n)
        {
            int i, p=3, t=1; q[1]=1; q[2]=2; sel[2]=true; nr=2;
            while (!sel[1])
            {
                while (sel[p]==true)
                {
                    if (p==n) t=-1;
                    p+=t;
                }
                while (nr>=2 && semn(a[q[nr-1]],a[q[nr]],a[p])==-1)
                {
                    sel[q[nr]]=false;
                    q[nr]=0; nr--;
                }
                q[++nr]=p;
                sel[p]=true;
            }
            nr--;
        }
        int main()
        {
            int n, i;
            freopen("infasuratoare.in","r",stdin);
            freopen("infasuratoare.out","w",stdout);
            scanf("%d",&n);
            for (i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);
            sort(a+1,a+n+1,cmp);
            solve(n); printf("%d\n",nr);
            for (i=1; i<=nr; i++) printf("%lf %lf\n",a[q[i]].x,a[q[i]].y);
            return 0;
        }