我也来传承了

P4468 [SCOI2007] 折纸

题目描述

求一张纸折 $n$ 次后 $m$ 个询问的坐标 $(x,y)$ 上有多少层纸。给出每次折痕两个端点的坐标。

解题思路

容易看出，正向模拟折纸过程十分复杂，所以可以从坐标点出发反向模拟折好的纸展开的过程。

对于每一个询问的坐标点，倒序模拟折痕，把纸展开，点映射在了纸片上的个数，就是该点穿过纸片的层数。

具体实现

用 dfs 倒序递归折痕，求出翻折后点的坐标。

注意：

• 点在直线右侧时不用翻折，因为折痕是把右边折向左边的。
• 求翻折点时折痕与坐标轴平行时不能求出斜率 $k$ 的值，所以特判出此类情况。
• 开 long double 确保精度。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define double long double
const int N=10;
const double eps=1e-14;
int ans;
struct node{
	double x,y;
	node(double a=0,double b=0){
		x=a,y=b;
	}
	friend node operator - (node a,node b){
		return node(a.x-b.x,a.y-b.y);
	}
	friend double operator * (node a,node b){//向量叉乘，用于判断点在半平面哪边
		return a.x*b.y-a.y*b.x;
	}
};
struct Node{
	node l,r;
}q[N];
int cal(node x){//对称后在纸片之内就是一层
	if(x.x<=0||x.x>=100||x.y<=0||x.y>=100) return 0;//题目说边界不算 
	return 1;
}
node sym(node x,Node line){
	node ans;
	if((line.r-line.l)*(x-line.l)<=eps) ans=x;//点在直线右侧
	else if(fabs(line.l.y-line.r.y)<eps){//直线与x轴平行时
		ans.x=x.x;
		ans.y=2*line.l.y-x.y;
	}
	else if(fabs(line.l.x-line.r.x)<eps){//直线与y轴平行时
		ans.x=2*line.l.x-x.x;
		ans.y=x.y;
	}
	else{
		double k=(line.l.y-line.r.y)/(line.l.x-line.r.x),b=line.l.y-k*line.l.x;//y=kx+b
		double k1=-1.0/k,b1=x.y-k1*x.x;
		ans.x=2*(b1-b)/(k-k1)-x.x;
		ans.y=k1*ans.x+b1;
	}
	return ans;
} 
void dfs(node x,int dep){
	if(!dep){
		ans+=cal(x);
		return;
	} 
	node y=sym(x,q[dep]);
	if(fabs(x.x-y.x)<eps&&fabs(x.y-y.y)<eps) return;//翻折后与原来重合 
	dfs(x,dep-1),dfs(y,dep-1);//本身和对称点都要算
}
int main(){
	int n,m;
	double x,y,x1,y1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>x1>>y1;
		q[i]={node(x,y),node(x1,y1)};
	}
	cin>>m;
	while(m--){
		cin>>x>>y;
		ans=0;
		dfs({x,y},n);//数据范围支持递归计算层数 
		cout<<ans<<endl;
	}
	return 0;
}