speike
speike
题目描述
众所周知,Speike 狗是一条特别喜欢追着Tom 打的狗。
现在,Tom 又把Speike 惹生气了,现在Speike 需要跨越千山万水找Tom 报仇。
Speike 所在的世界可以看成是一个无穷大的平面,平面由一个平面直角坐标系确定。在平面上有许多不相交的矩形障碍,矩形的四边平行于坐标轴。
Speike 需要从 (0,0)(0,0) 出发,在尽量短的时间内跑到 (X_t,0)(Xt,0),也就是Tom 在的位置。
出题人规定,Speike 只能沿着平行于坐标轴的方向运动,且不能进入矩形障碍的内部,但是可以在障碍边界上移动。
所有障碍的横坐标都在 [0,X_t][0,Xt] 之内。保证矩形不相交(即没有公共面积),也不会退化成线段或者点。
Speike 的智商不是很高,因此他需要你帮忙设计一条最短的路线。当然,你只需要告诉他路线的长度就行了。
输入格式
第一行一个整数 nn,代表障碍的个数。
第二行一个整数 X_tXt,代表终点的横坐标。
第三行开始,共 nn 行,每行4 个整数 a,b,c,da,b,c,d,代表每个矩形的某两个相对的顶点的坐标为 (a,b)(a,b) 和 (c,d)(c,d)
输出格式
共一行,一个整数,代表最短路线的长度。
样例
共下发三个样例,分别与第2; 4; 11 号测试点的数据范围与特性一致。
数据范围与提示
测试点编号 | n的范围 | 特殊性质 |
---|---|---|
1 | n \le 0n≤0 | 无 |
2,3 | n \le 1n≤1 | 无 |
4,5,6 | n \le 20n≤20 | a, b, c, d, X_{t} \in\left[-10^{3}, 10^{3}\right]a,b,c,d,Xt∈[−103,103] |
7,8,9,10 | n \le 200n≤200 | a, b, c, d, X_{t} \in\left[-10^{5}, 10^{5}\right]a,b,c,d,Xt∈[−105,105] |
11,12,13 | n \le 2000n≤2000 | a, b, c, d, X_{t} \in\left[-10^{3}, 10^{3}\right]a,b,c,d,Xt∈[−103,103] |
14,15 | n \le 2000n≤2000 | 无 |
16,17 | n \le 10^5n≤105 | 所有矩形都与xx轴相交 |
18,19,20 | n \le 5 \times 10^5n≤5×105 | nn有一定梯度 |
-10^{8} \leq a, c \leq X_{t} \leq 10^{8},-10^{8} \leq b, d \leq 10^{8}, n \in\left[0,10^{5}\right]−108≤a,c≤Xt≤108,−108≤b,d≤108,n∈[0,105]。
保证矩形不相交(即没有公共面积),每个矩形不会退化成线段或者点,且横坐标都在 [0,X_t][0,Xt] 之内。
来源
CSP-S 2019模拟 长沙一中2
Solution
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1000006
#define lb(x) lower_bound(Y+1,Y+m+1,x)-Y
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
using namespace std;
int n,ed,Y[maxn],f[maxn][],t;
int tr[maxn*];
struct node{
int a,b,c,d;
}s[maxn];
bool cmp(node A,node B){
return A.a<B.a;
}
void add(int k,int l,int r,int li,int ri,int v){
if(l>=li&&r<=ri){tr[k]=v;return;}
if(li<=mid)add(ls,l,mid,li,ri,v);
if(ri>mid)add(rs,mid+,r,li,ri,v);
}
void ask(int k,int l,int r,int pl){
t=max(t,tr[k]);
if(l==r)return;
if(pl<=mid)return ask(ls,l,mid,pl);
return ask(rs,mid+,r,pl);
}
int main(){
cin>>n>>ed;
for(int i=;i<=n;i++){
scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
if(s[i].a>s[i].c)swap(s[i].a,s[i].c);
if(s[i].b>s[i].d)swap(s[i].b,s[i].d);
Y[i]=s[i].d,Y[i+n]=s[i].b;
} int N=n+n+;Y[N]=;
sort(Y+,Y+N+);int m=unique(Y+,Y+N+)-Y-;
s[++n]=(node){ed,,ed,};
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++){
t=;ask(,,m,lb(s[i].b));
f[i][]=min(f[t][]+abs(s[t].b-s[i].b),f[t][]+abs(s[t].d-s[i].b));
t=;ask(,,m,lb(s[i].d));
f[i][]=min(f[t][]+abs(s[t].b-s[i].d),f[t][]+abs(s[t].d-s[i].d));
add(,,m,lb(s[i].b),lb(s[i].d),i);
}
cout<<f[n][]+ed<<endl;
return ;
}
最新文章
- Vue.js实现checkbox的全选和反选
- C++控制台贪吃蛇代码
- pyc 文件反编译 py uncompyle2
- Delphi 2010错误 "displayNotification: 内存不够"
- poj3259 bellman——ford Wormholes解绝负权问题
- space ship
- VBA Excel 常用 自定义函数
- Python教程:ORM连接Sqlite数据库,软件架构基础
- 在PHP中获取日期和时间
- iOS 辛格尔顿
- 10、ABPZero系列教程之拼多多卖家工具 拼团提醒逻辑功能实现
- javascript 调试 &; console.table()
- python处理Excel - xlrd xlwr openpyxl
- 小程序批量获取input的输入值,监听输入框,数据同步
- js 拷贝树copytree
- 移动端的rem适配
- Hadoop windows 环境配置
- 数据源(HikariCP)
- virtio-netdev 数据包的发送
- sublime text3控制台每次报错会显示几行[ ]