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

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

题意

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

思路

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

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

code

CPP

#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;
}
```

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

文章操作

题意

思路

code

相关推荐

评论

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