BZOJ1074/SCOI2007/折纸

Posted on By 二价氢

这里如果要模拟按照题目中所给的折线折成的纸的样子的话,会很蛋疼,所以我们考虑逆向思维,按照戳洞的位置倒退回去,看看纸上的洞在原来的什么位置

除开模板之外的内容,只有二十多行。

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结构体中重载了!运算符,用以判定点的合法性