P4468 [SCOI2007] 折纸 计算几何板子+dfs反推
P4468 [SCOI2007] 折纸
//P4468 [SCOI2007] 折纸
//数据很小，考虑暴搜
//思路：对于每次询问，根据最后一次折纸操作dfs一步步反推之前的状态，
// 相当于在折后的纸上对应点打孔，再通过dfs反推最初状态的点数，即为该点穿过的层数。
// 从后向前枚举每次的折痕，如果当前点在折痕左侧，则翻折前可以在折痕两侧都打了一个孔，dfs当前点和当前点关于折痕的对称点，
// 如果当前点在折痕右侧，则翻折后已经在这张纸外了，不用考虑（根据题意，若点在折痕上也不考虑）。
// 到dfs底层，即反推到了最初状态，判断每个点是否在原长方形纸片内部，累加符合条件的点，
// （若在外部则对应某次翻折后该点在纸片上但没有被折过来的纸片覆盖的情况，不考虑）。
//时间大概是O(m*2^n) （不确定）
//注意&易错
//1.写模板重载运算符的时候一定注意必须有返回值类型，如果不加似乎本地不会报错，但洛谷的测评机会CE
//2.有返回值的dfs必须每种情况都要考虑返回，开始没有在不符合所有情况时返回0，导致样例过不了（60pts）
//!!!!!!3.重载之后的运算每层最好都加括号！！！！不然会把挨着的没重载的小于号等判成没被重载的运算符（导致dfs判叉积的if里一直报错）
//4.为避免一些奇怪的错误，运算符重载的函数参数都加const且传要引用（我也不知道为什么qwq）
#include<bits/stdc++.h>
using namespace std;
const int eps=1e-8;
const double Pi=acos(-1.0);
int dcmp(double x){return (x<-eps)?-1:(x>eps?1:0);}//小于0返回-1 大于0返回1 等于0返回0
double Abs(double x){return x*dcmp(x);}
//Computer Graphics
namespace CG
{
struct pt{double x,y;pt(double tx=0,double ty=0){x=tx,y=ty;}};
inline bool cmpx(const pt &a,const pt &b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}//以x为第一关键字比较
typedef pt vec;//vec:向量，可以直接用点表示
inline double Len(const vec &a){return sqrt(a.x*a.x+a.y*a.y);}//向量的模长
inline double angle(const vec &a){return atan2(a.y,a.x);}//向量与x轴的夹角
inline vec operator +(const vec &a,const vec &b){return vec(a.x+b.x,a.y+b.y);}//向量加法
inline vec operator -(const vec &a,const vec &b){return vec(a.x-b.x,a.y-b.y);}//向量减法
inline vec operator *(const vec &a,const double b){return vec(a.x*b,a.y*b);}//向量数量积(重载参数)
inline vec operator /(const vec &a,const double b){return vec(a.x/b,a.y/b);}//向量数量积的逆运算（除法）(重载参数)
inline double operator *(const vec &a,const vec &b){return a.x*b.x+a.y*b.y;}//向量点积(重载参数)
inline double operator ^(const vec &a,const vec &b){return a.x*b.y-a.y*b.x;}//向量叉积-忽略了方向，只保留正负(重载参数)
inline vec rotate(vec a,double theta)//将向量绕原点逆时针旋转角theta的弧度
{return vec(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta));}
inline vec rotate_90(vec a){return vec(a.y,-a.x);}//向量绕原点逆时针旋转90度
inline pt rotate_p(pt a,pt b,double theta){return rotate(a-b,theta)+b;}//将点a绕点b旋转theta 实现方法相当于平移了坐标系
//命名技巧：点P(point)，线段S(segment)，射线R(ray)，直线L(line)
struct line{pt s,t;line(pt ts=pt(0,0),pt tt=pt(0,0)){s=ts,t=tt;}};//两端点表示一条线段
inline double maxx(const line &L){return max(L.s.x,L.t.x);}
inline double minx(const line &L){return min(L.s.x,L.t.x);}
inline double maxy(const line &L){return max(L.s.y,L.t.y);}
inline double miny(const line &L){return min(L.s.y,L.t.y);}
inline double angle(const line &L){return angle(L.t-L.s);}//直线与x轴的夹角(重载参数)
inline bool operator <(const line &a,const line &b)//判断b在a的逆时针方向(b与x轴的夹角更大)则返回真
{
//没有明白为什么要先判断角再用叉积判断 而且原博客似乎写错了
double a1=angle(a.t-a.s),a2=angle(b.t-b.s);
if(dcmp(a2-a1)!=0) return dcmp(a2-a1)>0;
else return dcmp((a.t-a.s)^(b.t-b.s));//似乎这里原博客错了
}
inline bool operator ==(pt a,pt b){return (!dcmp(a.x-b.x))&&(dcmp(a.y-b.y));}//判断两点是否重合
inline double dis_PP(pt a,pt b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}//两点距离
inline bool judge_PL(pt a,line b){return !dcmp((a-b.s)^(b.t-b.s));}//判断点是否在直线上(叉积为0)
inline bool judge_PS(pt a,line b){return (!dcmp((a-b.s)^(b.t-b.s)))&&(dcmp((a-b.s)*(a-b.t))<=0);}//判断点是否在线段上
inline pt Footpoint(pt a,line b)//点A在直线ST上的垂足
{
vec x=a-b.s,y=a-b.t,z=b.t-b.s;
double s1=x*z,s2=-1.0*(y*z);//AS、AT在ST上的投影 | 正负必须这么处理，以解决垂足不在线段b上的情况
return b.s+z*(s1/(s1+s2));//一次解决垂足在S左侧、线段b上、T右侧三种情况
}
inline pt mirror(pt a,line b){return a+(Footpoint(a,b)-a)*2.0;}//点a关于直线b的对称点
inline double dis_PL(pt a,line b){return Abs((a-b.s)^(a-b.t))/Len(b.t-b.s);}//点到直线的距离：面积除以底边长
inline double dis_PS(pt a,line b)//点到线段的距离
{
vec x=a-b.s,y=a-b.t,z=b.t-b.s;
if(dcmp(x*z)<0) return Len(x);//垂足在左端点左侧，a离左端点最近
if(dcmp(y*z)>0) return Len(y);//垂足在右端点右侧，a离右端点最近
return dis_PL(a,b);//垂足在线段上
}
inline pt point_PS(pt a,line b)//点a在线段b上距离最近的点
{
vec x=a-b.s,y=a-b.t,z=b.t-b.s;
if(dcmp(x*z)<0) return b.s;//垂足在左端点左侧，a离左端点最近
if(dcmp(y*z)>0) return b.t;//垂足在右端点右侧，a离右端点最近
return Footpoint(a,b);//垂足在线段上，垂足距离最近
}
inline pt cross_LL(line a,line b)//直线的交点
{
vec x=a.t-a.s,y=b.t-b.s,z=a.s-b.s;
return a.s+x*((y^z)/(x^y));//按照面积比找到交点在a上的位置，此处需要画图理解
}
inline bool judge_cross_SL(line a,line b)//判断线段a和直线b是否相交
{
if(!dcmp((a.t-a.s)^(b.t-b.s))) return false;//线段所在直线平行
return judge_PS(cross_LL(a,b),a);//两直线交点在a上
}
inline bool judge_cross_LL(line a,line b)//判断线段a和线段b是否相交
{
return judge_cross_SL(a,b)&&judge_cross_SL(b,a);//线段a与直线b相交且线段b与直线a相交 | 原博客判断方法有些复杂
}
}
using namespace CG;
line li[10];
int n,m,ans;
int dfs(pt p,int u)
{
if(u==0) return p.x>eps&&p.x<100&&p.y>eps&&p.y<100;//找到了翻折前的一个孔，若在原矩形内则累加答案
line tl=li[u];
if(((li[u].t-li[u].s)^(p-li[u].s))>0.0) return dfs(p,u-1)+dfs(mirror(p,tl),u-1);//！！！一定注意叉积后的结果打括号，不然报错
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&li[i].s.x,&li[i].s.y,&li[i].t.x,&li[i].t.y);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
double x,y;
scanf("%lf%lf",&x,&y);
pt p(x,y);
printf("%d\n",dfs(p,n));
}
return 0;
}