Cod sursa(job #1518741)

Utilizator gbibBacotiu Gabi gbib Data 6 noiembrie 2015 11:55:40
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <bits/stdc++.h>
#define eps 1e-12
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");

struct point{double x,y;int org;} vc[255];

bool cmp(point a, point b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
double aria(int n,point v[])
{int i;
if(n<3)
    return 0;
double sol=0;
sol += v[n].x*v[1].y - v[1].x*v[n].y;
for(i=1;i<=n;i++)
    sol+=v[i].x*v[i+1].y-v[i+1].x*v[i].y;
    sol=fabs(sol);
    return sol;
}
double cross_product(point o, point a, point b)
{
    a.x-=o.x;
    a.y-=o.y;
    b.x-=o.x;
    b.y-=o.y;
    return (a.x*b.y-a.y*b.x);
}
bool identic(point a,point b)
{
    return (a.x==b.x&&a.y==b.y);
}
double ch(int n,point vc[])
{
    int i,vf1;
    int cnt;
    point st[255],st1[255],st2[255],v[255];
    st1[1]=vc[1];
    st1[2]=vc[2];
    vf1=2;
    for(i=3;i<=n;i++)
    {
        while(vf1>=2&&cross_product(st1[vf1-1],st1[vf1],vc[i])<eps)
        {
            vf1--;
        }
        st1[++vf1]=vc[i];
    }
    int vf2;

    st2[1]=vc[n];
    st2[2]=vc[n-1];
    vf2=2;
    for(i=n-2;i>=1;i--)
    {
        while(vf2>=2&&cross_product(st2[vf2-1],st2[vf2],vc[i])<eps)
        {
            vf2--;
        }
        st2[++vf2]=vc[i];
    }

    for(i=1;i<=vf1;i++)
    {
    v[i]=st1[i];
    }
    for(i=2;i<vf2;i++)
    {
    v[i+vf1-1]=st2[i];
    }
    v[0].x=vf1+vf2-2;

    if(vf1+vf2-2<3)
        return 0;
    return aria(vf1+vf2-2,v);
}


void maibun(char a[])
{
    int lg=strlen(a),i;
    if(a[0]=='V')
    {
        for(i=0;i<lg;i++)
        {
            if(a[i]=='V')
                a[i]='I';
            else
            a[i]='V';
        }
    }
}

void build(point a[],point b[],char v[])
{
    int i,j;
    for(i=1;i<=a[0].x;i++)
    {
        v[a[i].org-1]='I';
    }
    for(i=1;i<=b[0].x;i++)
    {
        v[b[i].org-1]='V';
    }
}

void separat(int n,point p1, point p2, point a[],point b[])
{
    int i;
    int k1=0,k2=0;
        for(i=1;i<=n;i++)
        {
            if(cross_product(p1,p2,vc[i])<=0)
            {
                if(cross_product(p1,p2,vc[i])==0)
                {
                    if(identic(p1,vc[i]))
                        a[++k1]=vc[i];

                }
                if(cross_product(p1,p2,vc[i])<0)
                {
                    a[++k1]=vc[i];
                }
            }
            if(cross_product(p1,p2,vc[i])>=0)
            {
                if(cross_product(p1,p2,vc[i])==0)
                {
                    if(identic(p2,vc[i]))
                        b[++k2]=vc[i];
                }
                if(cross_product(p1,p2,vc[i])>0)
                {
                    b[++k2]=vc[i];
                }
            }
        }
    a[0].x=k1;
    b[0].x=k2;
}

int main()
{int i,j,n,n1=0,n2=0,ii,jj;
point st1[255],st2[255];
char c[255],bst[255];
double a1,a2,mini;
mini=1.0*(1<<30);
in>>n;
for(i=1;i<=n;i++)
{
    in>>vc[i].x>>vc[i].y;
    vc[i].org=i;
}

sort(vc+1,vc+n+1,cmp);

int ok1,ok2,ok3,ok4;
for(i=1;i<n;i++)
{
    for(j=1+i;j<=n;j++)
    {
        separat(n,vc[i],vc[j],st1,st2);
        ok1=ch(st1[0].x,st1);

        ok2=ch(st2[0].x,st2);
        if(ok1&&ok2)
        mini=min(fabs(ok1-ok2),mini);
        separat(n,vc[j],vc[i],st1,st2);


        ok3=ch(st1[0].x,st1);
        ok4=ch(st2[0].x,st2);
        if(ok3&&ok4)
        mini=min(fabs(ok3-ok4),mini);
    }
}
out<<mini/2.0<<'\n';

    return 0;
}