Cod sursa(job #86829)

Utilizator devilkindSavin Tiberiu devilkind Data 25 septembrie 2007 19:28:16
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#define NMAX 100000
#define INF 2000000000

struct punct{long int x,y;} pol[NMAX],min,pol2[NMAX],p1;

long int n,i,j,k,m,poz,x,y,nr,ymax,cnt;

long double ar,ar1,ar2,ar3;

inline long double det(punct p1, punct p2, punct p3)
{
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y -  p1.x*p3.y - p3.x*p2.y - p2.x*p1.y;
}

inline long double ab(long double x)
{
if (x<0) return -x;
return x;
}

long int cauta()
{
long int st,dr,mid;
long double d1,d2;

st=3;dr=cnt;

while (st<dr-1)
        {
        mid=(st+dr)/2;

        d1=det(pol[1],pol[mid],p1);
        d2=det(pol[1],pol[mid-1],p1);

        if (d1*d2<=0) return mid;
        if (d1<0) dr=mid;
                else st=mid;
        }
d1=det(pol[1],pol[st],p1);
d2=det(pol[1],pol[st-1],p1);

if (d1*d2<=0) return st;
return dr;
}


int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);

scanf("%ld %ld",&n,&m);

min.x=INF;min.y=INF;

for (i=1;i<=n;i++)
        {
        scanf("%ld %ld",&pol2[i].x,&pol2[i].y);

        if ((pol2[i].x<min.x)||((pol2[i].x==pol2[i].x)&&(pol2[i].y<min.y))) {min=pol2[i];poz=i;}
        }
pol[1].x=0;pol[1].y=0;
for (i=poz+1,j=2;i!=poz;i++,j++)
        {
        if (i>n) i-=n;

        pol[j]=pol2[i];
        pol[j].x-=min.x;
        pol[j].y-=min.y;
        if ((pol[j].x==0)&&(pol[j].y>ymax)) ymax=pol[j].y;
        }
nr=0;
cnt=n;
while (pol[cnt].x==0) cnt--;
for (i=1;i<=m;i++)
        {
        scanf("%ld %ld",&p1.x,&p1.y);

        p1.x-=min.x;p1.y-=min.y;

        if (p1.x<0) continue;
        if (p1.x==0) {
                     if (p1.y<=ymax) {nr++;/*printf("%ld %ld\n",p1.x+min.x,p1.y+min.y);*/}
                     continue;
                     }
        x=cauta();

        ar1=ab(det(pol[1],pol[x],p1)/2);
        ar2=ab(det(pol[1],pol[x-1],p1)/2);
        ar3=ab(det(pol[x],pol[x-1],p1)/2);
        ar=ab(det(pol[x],pol[x-1],pol[1])/2);

        if (ar1+ar2+ar3==ar) {nr++;/*printf("%ld %ld\n",p1.x+min.x,p1.y+min.y);*/}
        }

printf("%ld",nr);

return 0;

}