题意：给出一些直线，直线与直线切割的线段是围墙，只能从围墙中间穿过，问最少穿过几层墙才能到达终点
看到数据范围很小就开心地写了暴力找点+最短路，后来看了hzwer大神的题解才发现我还是太naive了...
这道题只要求从终点到外围直线与围墙的最少交点就能过！
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+100,maxm=1e6+100;
struct Point{
double x,y;
Point(double xx=0,double yy=0){
x=xx,y=yy;
}
}b[maxn],a[maxn],s[maxn],t[maxn],zhy,sa[4],ta[4];
struct Vector{
double x,y;
Vector(double xx=0,double yy=0){
x=xx,y=yy;
}
};
struct node{
int poi,bh;
}nh;
int n,m,v[maxm],w[maxm],nex[maxm],head[maxn],num,bj[maxn];
int dcmp(double x){return fabs(x)<1e-9?0:(x>0?1:-1);}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
Vector operator * (double p,Vector a){return Vector(a.x*p,a.y*p);}
bool operator < (Point a,Point b){return dcmp(a.x-b.x)==0?(dcmp(a.y-b.y)<0):(dcmp(a.x-b.x)<0);}
bool operator < (node a,node b){return a.poi>b.poi;}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
Point glt(Point a,Point b,Point c,Point d){
Vector v1=b-a,v2=d-c,v3=a-c;
return a+v2*v3/(v1*v2)*v1;
}
priority_queue<node>q;
void add(int x,int y){
v[++num]=y;
w[num]=1;
nex[num]=head[x];
head[x]=num;
v[++num]=x;
w[num]=1;
nex[num]=head[y];
head[y]=num;
}
bool segment(Point a,Point b,Point c,Point d,int ms=0){
Vector x=b-a,y=d-c;
Vector v1=c-a,v2=d-a;
if(ms&&dcmp(x*v1)*dcmp(x*v2)>0) return 0;
if(!ms&&dcmp(x*v1)*dcmp(x*v2)>=0) return 0;
v1=a-c,v2=b-c;
if(ms&&dcmp(y*v1)*dcmp(y*v2)>0) return 0;
if(!ms&&dcmp(y*v2)*dcmp(y*v1)>=0) return 0;
return 1;
}
void getdist(){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
bool ok=1;
for(int k=1;k<=m;k++)
if(segment(b[i],b[j],s[k],t[k])){
ok=0;
break;
}
if(ok&&j==n)
ok=1;
if(ok) add(i,j);
}
}
void dij(){
memset(bj,0x3f,sizeof(bj));
bj[0]=0;
nh.bh=0,nh.poi=0;
q.push(nh);
while(!q.empty()){
node now=q.top();
q.pop();
int x=now.bh,z=now.poi;
if(z>bj[x]) continue;
for(int i=head[x];i;i=nex[i])
if(bj[v[i]]>bj[x]+w[i]){
bj[v[i]]=bj[x]+w[i];
nh.bh=v[i],nh.poi=bj[v[i]];
q.push(nh);
}
}
printf("Number of doors = %d
",bj[n]-1);
}
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&t[i].x,&t[i].y);
sa[0]=Point(0,0),ta[0]=Point(0,100);
sa[1]=Point(0,0),ta[1]=Point(100,0);
sa[2]=Point(100,100),ta[2]=Point(0,100);
sa[3]=Point(100,100),ta[3]=Point(100,0);
for(int i=1;i<=m;i++){
num=0;
for(int j=1;j<=m;j++)
if(i!=j&&segment(s[i],t[i],s[j],t[j]))
a[++num]=glt(s[i],t[i],s[j],t[j]);
for(int j=0;j<4;j++)
if(segment(s[i],t[i],sa[j],ta[j],1))
a[++num]=glt(s[i],t[i],sa[j],ta[j]);
sort(a+1,a+num+1);
for(int i=1;i<num;i++)
b[++n]=Point((a[i].x+a[i+1].x)/2,(a[i].y+a[i+1].y)/2);
}
int k=n+1;
for(int i=0;i<4;i++){
num=0;
for(int j=1;j<=m;j++)
if(segment(sa[i],ta[i],s[j],t[j],1))
a[++num]=glt(sa[i],ta[i],s[j],t[j]);
for(int j=0;j<4;j++)
if(i!=j&&segment(sa[i],ta[i],sa[j],ta[j],1))
a[++num]=glt(sa[i],ta[i],sa[j],ta[j]);
sort(a+1,a+num+1);
for(int i=1;i<num;i++)
b[++n]=Point((a[i].x+a[i+1].x)/2,(a[i].y+a[i+1].y)/2);
}
num=1;
for(;k<=n;k++) add(0,k);
scanf("%lf%lf",&zhy.x,&zhy.y);
b[++n]=zhy;
getdist();
dij();
return 0;
}