题解 P3738 【[HAOI2014]穿越封锁线】

· · 题解

一道比较正常的计算几何题。

思路

思路很清晰，就是模拟先把所有点和边与y轴的交点排序，每次判断是否会导致这个点与多边形的位置关系（是否在多边形内）。

问题

第一反应肯定是“每穿过一条边或一个点与多边形位置关系都会改变”，然后收获一页WA。发现不是穿过每一个点时都会改变与多边形的位置关系。

解决方式

事实上这是因为点分两种，一种是像第一张图片一样，穿过会改变位置关系，另一种是像第二张图片，穿过不会改变位置关系，经过瞪眼认真思考，我们发现这是与连接这个点的两条线段与y轴正方向的位置关系决定的（此处将人的出发点作为原点）如果两条线段在y轴的同侧，则穿过点时不改变位置关系，反之则改变。

解决点的问题之后就是推出每条线段与y轴交点位置（如果有）并且统计。

注：还有一个坑点是初始位置可能在多边形内部，特判一下即可。

代码

代码中的“状态”即为点与多边形的位置关系。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=60;

struct node{
    double a;//交点y坐标 
    int flag;//是否改变状态 
}e[N];

int n,a,b,x[N],y[N],cnt,ans;
double now;

bool cmp(node x,node y){
    return x.a<y.a;
}

int main(){
    freopen("lg.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    scanf("%d%d",&a,&b);
    for(int i=1;i<=n;i++)
        x[i]-=a,y[i]-=b;//把人的初始坐标设为原点 
    x[0]=x[n],y[0]=y[n];
    for(int i=1;i<=n;i++){
        if(x[i]==0){//点 
            e[++cnt].a=y[i];
            e[cnt].flag=1;
            if((x[i-1]-x[i])*(x[i]-x[i+1])<0) e[cnt].flag=0;//如果连接一个点的两条边属于y轴同一侧则无需改变状态 
        }
        if(x[i]*x[i-1]<0){//边 
            if(x[i]>x[i-1])
                e[++cnt].a=(double)(y[i]-y[i-1])/(x[i]-x[i-1])*(-x[i-1])+y[i-1];
            else
                e[++cnt].a=(double)(y[i-1]-y[i])/(x[i-1]-x[i])*(-x[i])+y[i];//计算边与y轴交点坐标 
            e[cnt].flag=1;//一定会改变状态 
        }
    }
    double now=0,last=0;
    sort(e+1,e+cnt+1,cmp);
    for(int i=1,opt=0;i<=cnt;i++){
        if(e[i].flag){
            if(e[i].a<0){
                opt^=1;
                continue;
            } 
            if(opt)
                now+=e[i].a-last;
            else
                last=e[i].a;
            opt^=1;
        }
    }
    int ans=now;
    printf("%d\n",ans);
    return 0;
}