题意分析

题目背景

本题属于计算几何与图论的最短路径问题，描述考古学家在金字塔密室中寻找从外部到藏宝室的最优路径。关键在于通过几何计算确定最少需要炸开的门数。

核心问题

1. 密室结构：
   • 金字塔外围固定为$(0,0)-(0,100)-(100,100)-(100,0)$的矩形。
   • 内部有$n$道墙，每道墙连接两个外围墙，将空间分割为多个密室。
2. 炸门规则：
   • 门只能在墙的中点炸开。
   • 每次穿过一道墙需要炸开一扇门。
3. 目标：找到从外部到藏宝室穿墙次数最少的路径。

输入输出

• 输入：
  • $n$：内部墙的数量。
  • 每道墙的端点坐标$(x_1,y_1,x_2,y_2)$。
  • 藏宝室坐标$(s,t)$。
• 输出：最少需要炸开的门数，格式为Number of doors = X。

解题思路

1. 问题建模

• 几何表示：
  • 将每道墙视为线段，藏宝室视为点$P(s,t)$。
  • 从$P$向外引射线，计算与各墙的交点数量。
• 关键观察：
  • 最少穿墙数等于任意一条从$P$到外部路径中的最小交点数$+1$（至少穿过一堵外墙）。

2. 几何算法

1. 射线法：
   • 枚举所有外墙端点作为射线方向（避免与墙重合）。
   • 对每条射线，统计其与所有内墙的有效交点（在线段范围内）。
2. 交点判断：
   • 使用向量叉积判断线段与射线的相交：$$\text{相交} \iff ((\vec{PA} \times \vec{PB}) \cdot (\vec{PC} \times \vec{PD}) > 0) $$其中$A,B$为墙端点，$C,D$为射线方向点。
   • 检查交点是否在线段范围内（坐标区间判断）。

3. 优化与验证

• 避免重复计算：预处理墙的端点坐标。
• 边界处理：确保射线不与任何墙平行或重合。

算法实现

代码框架

#include<bits/stdc++.h> 
#define ll long long
#define db double
using namespace std;

int n,nn,cnt,ans;
double s,t;

struct node{
	db x,y,xx,yy;
}f[100],v[100];

db work(node a,node b,node c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool hh(node a,node b,node c)
{
	if(c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x)&&c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y))
		return 1;
	return 0;
}

bool check(db ax,db ay,db bx,db by,db cx,db cy,db dx,db dy)
{
	node a,b,c,d;
	a.x=ax,a.y=ay,b.x=bx,b.y=by,c.x=cx,c.y=cy,d.x=dx,d.y=dy;
	if((work(a,c,b)*work(a,b,d)>0)&&(work(c,b,d)*work(c,d,a)>0))
		return 1;


	return 0;
}

int main(){
	scanf("%d",&n);
	nn=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf%lf",&f[i].x,&f[i].y,&f[n+i].x,&f[n+i].y);
		v[i].x=f[i].x,v[i].y=f[i].y,v[i].xx=f[i+n].x,v[i].yy=f[i+n].y;
	}
	n=n*2;
	f[++n].x=0,f[n].y=0;
	f[++n].x=0,f[n].y=100;
	f[++n].x=100,f[n].y=0;
	f[++n].x=100,f[n].y=100;
	scanf("%lf%lf",&s,&t);
	ans=1e9;
	for(int i=1;i<=n;i++)
	{
		int w=0;
		for(int j=1;j<=nn;j++)
		{
			if(check(f[i].x,f[i].y,s,t,v[j].x,v[j].y,v[j].xx,v[j].yy))
				w++;
		}
		ans=min(ans,w);
	}
	printf("Number of doors = %d",ans+1);
}

关键步骤

1. 输入处理：读取墙和藏宝室坐标。
2. 射线枚举：遍历所有外墙端点作为射线方向。
3. 交点统计：对每条射线，检查与每道内墙的交点。
4. 结果计算：取最小交点数$+1$。

复杂度分析

• 时间：$O(n \cdot k)$，其中$n$为内墙数，$k=4$（外墙端点数量）。
• 空间：$O(n)$，存储墙数据。