题意:
有一个左下角为 \((0,0)\),右上角为 \((100,100)\) 的正方形,给你 \(n\) 个有向线段和 \(m\) 个询问,将纸片依次按直线折叠,然后每次询问让你求出某个点上有多少层纸。
分析:
观察到数据范围非常小,于是可以直接对于每个询问 \(\mathcal{O}(2^n)\) 来求。
具体的,对于每一个点,倒着枚举 \(n\) 条直线。
如果这个点在直线的左边,那么就继续递归这个点和这个点关于直线的对称点;如果在右边,那么这个点就不在纸上,直接结束递归。
最后只需要看有多少个点在 \((0,0)\) 到 \((100,100)\) 内即可。
而在代码中,我用的是 \(y=kx+b\) 的形式来表示一条直线,这样子要求对称的话就只需要根据垂直的线 \(k\) 相乘为 \(-1\),就可以求出垂足,然后再求对称即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 55;
const double eps = 1e-6;
int n,m,ans;
struct point
{
double x,y;
friend point operator-(point x,point y){return {x.x-y.x,x.y-y.y};}
friend double operator*(point x,point y){return x.x*y.y-x.y*y.x;}
}p[N][2];
struct line{double k,b;}l[N];
line f(point p1,point p2)//将用两个点表示直线转化为用y=kx+b表示的形式
{
if(p1.x == p2.x)return {1e9,p1.x};
line ans;
ans.k = (p1.y-p2.y)/(p1.x-p2.x);
ans.b = p1.y-ans.k*p1.x;
return ans;
}
point jiao(line l1,line l2)//求两直线的交点
{
point ans;ans.x = (l2.b-l1.b)/(l1.k-l2.k);
ans.y = l1.k*ans.x+l1.b;
return ans;
}
point chuizu(point p1,line l1)//求垂足
{
if(fabs(l1.k) < eps)return {p1.x,l1.b};
if(l1.k == 1e9)return {l1.b,p1.y};
line l2;l2.k = -1/l1.k;l2.b = p1.y-l2.k*p1.x;
return jiao(l1,l2);
}
point mirror(point p1,point p2){return {p2.x*2-p1.x,p2.y*2-p1.y};}//对称点
bool pd(point now,point x,point y){return (y-x)*(now-x) > eps;}//用叉积判断一个点是否在直线左边
bool check(point now){return now.x > eps&&now.x < 100-eps&&now.y > eps&& now.y < 100-eps;}//判断点是否在原正方形内
void dfs(int x,point now)
{
if(!x)return (void)(ans += check(now));
point nex = mirror(now,chuizu(now,l[x]));
if(pd(now,p[x][0],p[x][1]))dfs(x-1,now),dfs(x-1,nex);
}
inline double rd(){double x;scanf("%lf",&x);return x;}
int main()
{
n = rd();
for(int i = 1;i <= n;i++)
{
p[i][0] = {rd(),rd()};p[i][1] = {rd(),rd()};
l[i] = f(p[i][0],p[i][1]);
}
m = rd();
while(m--)
{
point x = {rd(),rd()};ans = 0;
dfs(n,x);
printf("%d\n",ans);
}
return 0;
}
标签:now,p1,return,point,题解,ans,折纸,l1,SCOI2007
From: https://www.cnblogs.com/max0810/p/18329537