Cod sursa(job #1397060)

Utilizator iarbaCrestez Paul iarba Data 23 martie 2015 11:27:27
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
using namespace std;
long long rez,rez2;
int next[100001],prev[100001],ax[100001],ay[100001],qx[100001],qy[100001];
int n,m,i,j,x,y,p,ps,pd;
long long arie(int c1, int c2, long long x, long long y)
{
    long long aux1,aux2;
    aux1=ax[c1];
    aux2=ay[c2];
    long long r1=aux1*aux2-x*aux2;
    aux1=ax[c2];
    aux2=ay[c1];
    long long r2=aux1*y-aux1*aux2;
    aux1=ax[c1];
    aux2=ay[c1];
    long long r3=x*aux2-aux1*y;
    long long rezultat=r1+r2+r3;
    return rezultat;
}
int main()
{
    freopen("geometrie.in","r",stdin);
    freopen("geometrie.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&ax[i],&ay[i]);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&qx[i],&qy[i]);
    }
    ax[n+1]=1000000002;qx[m+1]=1000000002;
    rez=0;
    next[1]=2;prev[1]=2;
    next[2]=1;prev[2]=1;
    i=3;
    j=1;
    while(qx[j]<=ax[2]){printf("0.0\n");j++;}
    while(j<=m)
    {
        if(ax[i]<qx[j])
        {

            x=ax[i];
            y=ay[i];
            p=i-1;
            if((arie(prev[p],p,x,y)==0)&&(arie(p,next[p],x,y)==0))
            {
                next[1]=i;prev[1]=i;
                next[i]=1;prev[i]=1;
            }
            else
            {
                ps=p;
                while(arie(prev[ps],ps,x,y)>=0){rez+=arie(prev[ps],ps,x,y);ps=prev[ps];}
                pd=p;
                while(arie(pd,next[pd],x,y)>=0){rez+=arie(pd,next[pd],x,y);pd=next[pd];}
                next[ps]=i;prev[i]=ps;
                prev[pd]=i;next[i]=pd;
            }
            i++;
        }
        else
        {

            x=qx[j];
            y=qy[j];
            p=i-1;
            if((arie(prev[p],p,x,y)==0)&&(arie(p,next[p],x,y)==0))
            {
                printf("0.0\n");
            }
            else
            {
                rez2=rez;
                ps=p;
                while(arie(prev[ps],ps,x,y)>=0){rez2+=arie(prev[ps],ps,x,y);ps=prev[ps];}
                pd=p;
                while(arie(pd,next[pd],x,y)>=0){rez2+=arie(pd,next[pd],x,y);pd=next[pd];}
                printf("%I64d",rez2/2);
                if(rez2%2){printf(".5\n");}
                else{printf(".0\n");}
            }
            j++;
        }
    }
return 0;
}