题解：P13752 【MX-X17-T1】Walk,Walk,Walk

shq112 · 2025-08-17 20:14:19 · 题解

本蒟蒻的第一篇题解
题目传送门

题意

对于n条线和2个点，求从第一个点到第二个点的路程中，最少穿过n条线中多少条线。

思路

我们仔细看题不难发现，如果这两个点在某一条直线两侧，从一个点到另一个点的路程一定穿过这条直线。
也就是说如果一条直线的x/y坐标在两点的x/y坐标范围之内，两点的路径就 一定穿过这条直线

所以我们只需要遍历两点的x/y坐标范围并记录在此范围内的直线的数量，即可AC

code

#include<bits/stdc++.h>
using namespace std;
long long n,t,k,sx,sy,tx,ty,xl[100001],yl[100001],ans,xsiz=0,ysiz=0;
bool cmp(long long x,long long y){
    return x>y;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t>>k;//输入
        if(t==1){
            xl[++xsiz]=k;记录平行于x,y轴的直线
        }else{
            yl[++ysiz]=k;
        }
    }
    sort(yl+1,yl+ysiz+1,cmp);
    sort(xl+1,xl+xsiz+1,cmp);//这两行其实没用
    cin>>sx>>sy>>tx>>ty;
    for(int i=1;i<=ysiz;i++){
        if(yl[i]>=sy&&yl[i]<=ty||yl[i]>=ty&&yl[i]<=sy){
            ans++;
        }
    for(int i=1;i<=xsiz;i++){
        if(xl[i]>=sx&&xl[i]<=tx||xl[i]>=tx&&xl[i]<=sx){
            ans++;
        }//如果直线在两点之间，ans就++
    }
    }cout<<ans;
    return 0;
}
```