Cod sursa(job #889355)

Utilizator marinutzacatana marina marinutza Data 24 februarie 2013 14:10:43
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.49 kb
#include<cstdio>
using namespace std;
#define nmax 120010
struct pct
{
    double x;
    double y;
} a[nmax],A,B,C,D;
int n,ok[nmax],s[nmax],qp[7],q,l,tginf,i,k;
double tg;
int ap_dr(pct a,pct b,pct c)
{
    pct z;
    if(a.x>b.x)
    {
        z.x=a.x;
        z.y=a.y;
        a.x=b.x;
        a.y=b.y;
        b.x=z.x;
        b.y=z.y;
    }
    if(a.y>b.y)
    {
        if(c.x>=a.x && c.x<=b.x && c.y<=a.y && c.y>=b.y)
            return 1;
        else
            return 0;
    }
    else
    {
        if(c.x>=a.x && c.x<=b.x && c.y<=b.y && c.y>=a.y)
            return 1;
        else
            return 0;
    }
}
int main()
{
    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);
        if(i==1)
        {
            A.x=B.x=C.x=D.x=a[i].x;
            A.y=B.y=C.y=D.y=a[i].y;
            qp[1]=qp[2]=qp[3]=qp[4]=qp[5]=1;
        }
        if(A.y>a[i].y || (A.y==a[i].y && A.x>a[i].x))
        {
            A.x=a[i].x;
            A.y=a[i].y;
            qp[1]=qp[5]=i;
        }
        if(B.x<a[i].x || (B.x==a[i].x && B.y>a[i].y))
        {
            B.x=a[i].x;
            B.y=a[i].y;
            qp[2]=i;
        }
        if(C.y<a[i].y || (C.y==a[i].y && C.x<a[i].x))
        {
            C.x=a[i].x;
            C.y=a[i].y;
            qp[3]=i;
        }
        if(D.x>a[i].x || (D.x==a[i].x && D.y<a[i].y))
        {
            D.x=a[i].x;
            D.y=a[i].y;
            qp[4]=i;
        }
    }
    s[++k]=qp[1];
    ok[qp[1]]=1;
    pct p1,p2,p3;
    p1.x=A.x;
    p1.y=A.y;
    p2.x=B.x;
    p2.y=B.y;
    l=2;
    //tginf=1;
    while(ok[qp[1]]!=2)
    {
        tg=120000;
        for(i=1;i<=n;i++)
        {
            if((ok[i]!=1 && ap_dr(p1,p2,a[i])) || (i==qp[1] && p1.x!=A.x && p1.y!=A.y))
            {
                if(a[i].x-p1.x==0)
                {
                    if((p3.y<a[i].y && l==3) || (p3.y>a[i].y && l==5) || tginf==0)
                    {
                        p3.x=a[i].x;
                        p3.y=a[i].y;
                        q=i;
                        tginf=1;
                    }
                }
                if(a[i].x-p1.x!=0 && tginf==0)
                {
                    if((a[i].y-p1.y)/(a[i].x-p1.x)<tg)
                    {
                        tg=(a[i].y-p1.y)/(a[i].x-p1.x);
                        p3.x=a[i].x;
                        p3.y=a[i].y;
                        q=i;
                    }
                    else
                    {
                        if((a[i].y-p1.y)/(a[i].x-p1.x)==tg)
                        {
                            if((a[i].y>p3.y && l==3) || (a[i].y<p3.y && l==5))
                            {
                                p3.x=a[i].x;
                                p3.y=a[i].y;
                                q=i;
                            }
                        }
                    }
                }
            }
        }
        s[++k]=q;
        ok[q]++;
        tginf=0;
        if(p3.x==p2.x && p3.y==p2.y)
        {
            p1.x=p2.x;
            p1.y=p2.y;
            p2.x=a[qp[++l]].x;
            p2.y=a[qp[l]].y;
        }
        else
        {
            p1.x=p3.x;
            p1.y=p3.y;
        }

    }
    printf("%d\n",k-1);
    for(i=1;i<k;i++)
        printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);
    return 0;
}