Cod sursa(job #1516672)

Utilizator gbibBacotiu Gabi gbib Data 3 noiembrie 2015 12:57:28
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.86 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 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 diferit(point a,point b)
{
    return !(a.x==b.x&&a.y==b.y);
}
bool ch(int n,int s,point e,point v[],point p1,point p2)
{
    int i,vf1;
    int cnt;
    point st[255],st1[255],st2[255];
    vf1=0;
    for(i=1;i<=n;i++)
    if(s==1)
    {
        if(cross_product(p1,p2,vc[i])<eps&&diferit(e,vc[i]))
        {

        while(vf1>=2&&cross_product(st1[vf1-1],st1[vf1],vc[i])<eps)
        {
            vf1--;
        }
        st1[++vf1]=vc[i];
        }
    }
    else
    {
        if(cross_product(p1,p2,vc[i])>(-eps)&&diferit(e,vc[i]))
        {

        while(vf1>=2&&cross_product(st1[vf1-1],st1[vf1],vc[i])<eps)
        {
            vf1--;
        }
        st1[++vf1]=vc[i];
        }
    }
    int vf2;

    vf2=0;
    for(i=n;i>=1;i--)
    if(s==1)
    {
        if(cross_product(p1,p2,vc[i])<eps&&diferit(e,vc[i]))
        {
        while(vf2>=2&&cross_product(st2[vf2-1],st2[vf2],vc[i])<eps)
        {
            vf2--;
        }
        st2[++vf2]=vc[i];
        }
    }
    else
    {
        if(cross_product(p1,p2,vc[i])>(-eps)&&diferit(e,vc[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;
    for(i=1;i<=vf1+vf2-2;i++)
    {
        //out<<v[i].org<<" ";
    }
    //out<<'\n';
    if(vf1+vf2-2<3)
        return 0;
    return 1;
}


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;
}

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';
    }
}


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++)
    {
        //out<<i<<"(in doua) "<<j<<"(in prima) "<<'\n';
        //out<<"{\n";
        //out<<"prima: ";
        ok1=ch(n,1,vc[i],st1,vc[i],vc[j]);
        if(ok1)
        a1=aria(st1[0].x,st1);
        //out<<"doua: ";
        ok2=ch(n,0,vc[j],st2,vc[i],vc[j]);
        if(ok2)
        a2=aria(st2[0].x,st2);
       // out<<'}';
       // out<<'\n';
        if(fabs(a1-a2)<mini&&fabs(a1-a2)&&ok1&&ok2)
        {
            mini=fabs(a1-a2);
        }
       //out<<i<<"(in prima) "<<j<<"(in doua) "<<'\n';
        //out<<"[\n";
        //out<<"prima: ";
        ok3=ch(n,1,vc[j],st1,vc[i],vc[j]);
        if(ok3)
        a1=aria(st1[0].x,st1);
       // out<<"doua: ";
        ok4=ch(n,0,vc[i],st2,vc[i],vc[j]);
        if(ok4)
        a2=aria(st2[0].x,st2);
       // out<<']';
       // out<<'\n';
        if(fabs(a1-a2)<mini&&fabs(a1-a2)&&ok3&&ok4)
        {
            mini=fabs(a1-a2);
        }
    }
}
out<<mini/2<<'\n';

    return 0;
}