题解：P9875 [EC Final 2021] Two Walls

· · 题解

首先可以尝试一下，可以发现答案只有三种：0,1,2。但是不知道应该怎么证明。下面我们分别来讨论几种情况：

两个墙没有相交（包括有部分重合）：

显然他最多拐一次，只需要判断线段 ab 是否经过墙就可以了。

两个墙相交：

先看这个：对于一个点和一个墙，绿色部分是不能走的。

所以两堵墙不能走的区域就是这样的：

可以发现，只要两个点可以到达的区域有交集就只拐一次就可以了，否则就需要拐两次。

这两个区域有交集可以转化为 a 与 b 分别与同侧的墙的端点的射线是否有交点，具体的话可以看图：

具体可以这样，先判断 a 和 b 分别在两个线段分割的四个区域的那个部分，然后枚举 a 和 b 连对应区域的墙的两个点射线有没有交点，有就是 1，没有就是 2。

所以判断的顺序可以是这样：

思路已经很清楚了，还有一些细节的实现：

先给几个前置的知识：

int sgn(__int128_t x){return x==0?0:(x<0?-1:1);}//sgn函数，只取符号 
struct point{
    __int128_t x,y;
    point operator -(const point & p)const{return {x-p.x,y-p.y};}//求向量 
}
__int128_t cross(point a,point b){return a.x*b.y-a.y*b.x;}//向量叉乘 
int F(point a,point b,point c){return sgn(cross(b-a,c-a));}//判断c在ab的哪一侧

怎么判断两个线段是否相交

若两线段 a,b 相交，b 线段的两个端点一定分布在 a 线段所在直线两侧，同时 a 线段的两个端点一定分布在 b 线段所在直线两侧。我们可以直接判断一条线段的两个端点相对于另一线段所在直线的位置关系。

bool jiao(point a,point b,point c,point d){
    if(F(a,b,c)*F(a,b,d)>=0)return 0;//cd在ab同侧 
    if(F(c,d,a)*F(c,d,b)>=0)return 0;//ab在cd同侧 
    return 1;//ab与cd相交 
}

两个射线是否相交

提前在给参数的时候把射线的方向规定好就行了，最后返回那部分那个正负必须这样规定，不然交点会在射线另一侧。

bool jiao2(point a,point b,point c,point d){
    int sg=sgn(cross(b-a,d-c));//向量ab和cd叉乘 
    if(sg==0)return 0;//平行 
    return F(c,d,a)==sg && F(a,b,c)==-sg;//类似于零点存在性的证明，一个在他下面一个在他上面，而且连续所以相交。
}

怎么判断一个点是否在一个线段上

首先要保证点的 x 在线段的定义域，y 在线段的值域上，并且点在线段所在的直线上就可以保证点在线段上。

bool onLine(point a,point b,point c){//判断c是否在线段ab上 
    if(c.x<min(a.x,b.x)||c.x>max(a.x,b.x))return 0;//c的x属于线段ab的x的范围 
    if(c.y<min(a.y,b.y)||c.y>max(a.y,b.y))return 0;//c的y属于线段ab的y的范围 
    return cross(c-a,c-b)==0;//c在直线ab上 
}

代码：

#include<bits/stdc++.h>
using namespace std;
struct point{
    __int128_t x,y;
    point operator -(const point & p)const{return {x-p.x,y-p.y};}//求向量 
}a,b,c,d,e,f;
void read(point &a){//读入 
    int x,y;
    scanf("%d%d",&x,&y);
    a.x=x,a.y=y;
}
__int128_t cross(point a,point b){return a.x*b.y-a.y*b.x;}//向量叉乘 
int sgn(__int128_t x){return x==0?0:(x<0?-1:1);}//sgn函数，只取符号 
int F(point a,point b,point c){return sgn(cross(b-a,c-a));}//判断c在ab的哪一侧 
bool jiao(point a,point b,point c,point d){
    if(F(a,b,c)*F(a,b,d)>=0)return 0;//cd在ab同侧 
    if(F(c,d,a)*F(c,d,b)>=0)return 0;//ab在cd同侧 
    return 1;//ab与cd相交 
}
bool jiao2(point a,point b,point c,point d){
    int sg=sgn(cross(b-a,d-c));//向量ab和cd叉乘 
    if(sg==0)return 0;//平行 
    return F(c,d,a)==sg && F(a,b,c)==-sg;//类似于零点存在性的证明，一个在他下面一个在他上面，而且连续所以相交 
}
bool onLine(point a,point b,point c){//判断c是否在线段ab上 
    if(c.x<min(a.x,b.x)||c.x>max(a.x,b.x))return 0;//c的x属于线段ab的x的范围 
    if(c.y<min(a.y,b.y)||c.y>max(a.y,b.y))return 0;//c的y属于线段ab的y的范围 
    return cross(c-a,c-b)==0;//c在直线ab上 
}
int work(){
    vector<point>X,Y;
    if(onLine(a,b,c)||onLine(a,b,d)||onLine(a,b,e)||onLine(a,b,f))return 1;//ab线段上正好有墙的一头 
    if(!jiao(a,b,c,d)&&!jiao(a,b,e,f))return 0;//线段ab不经过线段cd和线段ef 
    if(!jiao(c,d,e,f))return 1;//两个墙不相交 
    for(point p:{c,d}){//判断a和b分别在两个线段分割的四个区域的那个部分
        if(!jiao(a,p,e,f))X.push_back(p);
        if(!jiao(b,p,e,f))Y.push_back(p);
    }
    for(point p:{e,f}){
        if(!jiao(a,p,c,d))X.push_back(p);
        if(!jiao(b,p,c,d))Y.push_back(p);
    }//看射线是否相交
    for(auto i:X)for(auto j:Y)if(jiao2(a,i,b,j))return 1;
    return 2;
}
int main(){
    int T;
    for(scanf("%d",&T);T--;printf("%d\n",work()))read(a),read(b),read(c),read(d),read(e),read(f);
    return 0;
}

附记：从一月末就开始写这篇题解了，拖到现在才写完，2735你不能这样颓废了。