Cod sursa(job #1395825)

Utilizator iarbaCrestez Paul iarba Data 21 martie 2015 15:55:51
Problema A+B Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 2.1 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)
{
    return (long long)ax[c1]*ay[c2]+ax[c2]*y+x*ay[c1]-x*ay[c2]-ax[c2]*ay[c1]-ax[c1]*y;
}
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("%lld",rez2/2);
                if(rez2%2){printf(".5\n");}
                else{printf(".0\n");}
            }
            j++;
        }
    }
return 0;
}