这里如果要模拟按照题目中所给的折线折成的纸的样子的话,会很蛋疼,所以我们考虑逆向思维,按照戳洞的位置倒退回去,看看纸上的洞在原来的什么位置
除开模板之外的内容,只有二十多行。
int lc,n;
int dfscheck(Point t,int d)
{
if (d<0)
return !t;
double flag(Point(t.x-L[d].a.x,t.y-L[d].a.y)&Point(L[d].b.x-L[d].a.x,L[d].b.y-L[d].a.y));
return (_ge(flag,0))?(0):(dfscheck(t,d-1)+dfscheck(L[d]*t,d-1));
}
int main()
{
Point p;
scanf("%d",&lc);
for (int i=0;i<lc;i++)
{
scanf("%lf%lf%lf%lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y);
}
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%lf%lf",&p.x,&p.y);
printf("%d\n",dfscheck(p,lc-1));
}
}
当然,在Point
结构体中重载了!
运算符,用以判定点的合法性