Pagini recente » Cod sursa (job #2257629) | Cod sursa (job #1538) | Cod sursa (job #1992033) | Cod sursa (job #1661487) | Cod sursa (job #127765)
Cod sursa(job #127765)
#include <stdio.h>
#define Nmax 808
struct punct { int x, y; };
struct line { int l; double m; };
int N,M,i,tot;
punct P[Nmax],W;
int sx[Nmax]; //punctele sortate dupa x
line L[Nmax][Nmax]; //liniile care intersecteaza o zona
int nr[Nmax]; //numarul de linii care intersecteaza o zona
int a[Nmax],b[Nmax],c[Nmax]; //coeficientii
void qsort(int st,int dr)
{
int i=st,j=dr,m=sx[(st+dr)>>1],aux;
while (i<=j)
{
while (sx[i]<m) ++i;
while (m<sx[j]) --j;
if (i<=j)
{
aux=sx[i];sx[i]=sx[j];sx[j]=aux;
++i;--j;
}
}
if (i<dr) qsort(i,dr);
if (st<j) qsort(st,j);
}
void qsortlines(int ind,int st,int dr)
{
int i=st,j=dr;
double m=L[ind][(st+dr)>>1].m;
line aux;
while (i<=j)
{
while (L[ind][i].m<m) ++i;
while (m<L[ind][j].m) --j;
if (i<=j)
{
aux=L[ind][i];L[ind][i]=L[ind][j];L[ind][j]=aux;
++i;--j;
}
}
if (i<dr) qsortlines(ind,i,dr);
if (st<j) qsortlines(ind,st,j);
}
void build()
{
int i,j;
double alfa,xx,yy;
for (i=1;i<N;++i)
if (sx[i]!=sx[i+1])
for (j=1;j<=N;++j)
if (((P[j].x<=sx[i])&&(P[j+1].x>=sx[i+1])) || ((P[j+1].x<=sx[i])&&(P[j].x>=sx[i+1])))
{
if (P[j+1].y==P[j].y) yy=P[j].y;
else
{
alfa=(double)(P[j+1].x-P[j].x)/(P[j+1].y-P[j].y);
xx=(double)(sx[i+1]+sx[i])/2-P[j].x;
yy=(double)P[j].y+xx/alfa;
}
L[i][++nr[i]].l=j;
L[i][nr[i]].m=yy;
}
}
void cauta()
{
int st=0,dr=N,lo,hi,m,aux;
//cauta banda
while (st+1<dr)
{
m=(st+dr)>>1;
if (sx[m]<W.x) st=m;
else dr=m;
}
while ((sx[st+1]<W.x)&&(st<=N)) ++st;
while ((sx[st]==sx[st+1])&&(st<=N)) ++st;
if ((st==0)||(st>=N)) return;
//cauta deasupra cator drepte se afla
lo=1;hi=nr[st];
while (lo+1<hi)
{
m=(lo+hi)>>1;
if (P[L[st][m].l].x<P[L[st][m].l+1].x) aux=1;
else aux=-1;
if ((double)(aux*(a[L[st][m].l]*W.x+b[L[st][m].l]*W.y+c[L[st][m].l]))>0) lo=m;
else hi=m;
}
//ups and downs
m=lo;
if (P[L[st][m].l].x<P[L[st][m].l+1].x) aux=1;
else aux=-1;
if ((double)aux*(a[L[st][m].l]*W.x+b[L[st][m].l]*W.y+c[L[st][m].l])<0) --m;
if (P[L[st][m+1].l].x<P[L[st][m+1].l+1].x) aux=1;
else aux=-1;
if ((double)aux*(a[L[st][m+1].l]*W.x+b[L[st][m+1].l]*W.y+c[L[st][m+1].l])>0) ++m;
//se afla deasupra unui nr impar de drepte
if (m&1) ++tot;
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
scanf("%d %d",&N,&M);
for (i=1;i<=N;++i)
{
scanf("%d %d",&P[i].x,&P[i].y);
sx[i]=P[i].x;
}
P[N+1]=P[1];
for (i=1;i<=N;++i)
{
a[i]=P[i].y-P[i+1].y;
b[i]=P[i+1].x-P[i].x;
c[i]=P[i].x*P[i+1].y-P[i+1].x*P[i].y;
}
qsort(1,N);
build();
for (i=1;i<N;++i)
if (sx[i]!=sx[i+1])
qsortlines(i,1,nr[i]);
for (i=0;i<M;++i)
{
scanf("%d %d",&W.x,&W.y);
cauta();
}
printf("%d",tot);
fclose(stdout);
fclose(stdin);
return 0;
}