【蓝桥杯集训·每日一题2025】 AcWing 5590. 沿栅栏散步 python

devtools/2025/3/15 23:47:36/



AcWing 5590. 沿栅栏散步

Week 4
3月11日

题目描述

农夫约翰有 N N N 头奶牛,每头奶牛都喜欢日常沿着包围牧场的栅栏散步。

栅栏由 P P P 根柱子组成( P P P 为偶数),每根柱子的位置是农夫约翰农场地图上的一个不同的二维坐标点 ( x , y ) (x,y) (x,y)

每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子,因此整个栅栏可以被视为各边平行于 x x x 轴或 y y y 轴的一个多边形(最后一根柱子连回第一根柱子,确保围栏形成一个包围牧场的闭环)。

栅栏多边形是「规则的」,体现在栅栏段仅可能在其端点处重合,每根柱子恰好属于两个栅栏段,同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置,均为沿栅栏的某个点(可能在柱子处,也可能不在)。

每头奶牛日常散步时沿着栅栏行走,从起始位置开始,到结束位置结束。

由于栅栏形成闭环,奶牛有两条路线可以选择。

由于奶牛是一种有点懒的生物,每头奶牛都会选择距离较短的方向沿栅栏行走(如果并列,奶牛可以选择任一方向)。

输入格式

输入的第一行包含 N N N P P P

以下 P P P 行的每一行包含两个整数,以顺时针或逆时针顺序表示栅栏柱子的位置。

以下 N N N 行的每一行包含四个整数 x 1 , y 1 , x 2 , y 2 x_1, y_1, x_2, y_2 x1,y1,x2,y2,表示一头奶牛的起始位置 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和结束位置 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)

输出格式

输出 N N N 个整数,为每头奶牛行走的距离。

数据范围

1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1N105,
4 ≤ P ≤ 2 × 1 0 5 4 \le P \le 2 \times 10^5 4P2×105,
0 ≤ x , y ≤ 1000 0 \le x,y \le 1000 0x,y1000

输入样例:
5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0
输出样例:
2
3
3
4
4
样例解释

第一头奶牛可以直接从 ( 0 , 0 ) (0,0) (0,0) 走到 ( 0 , 2 ) (0,2) (0,2)

第二头奶牛可以从 ( 0 , 2 ) (0,2) (0,2) 走到 ( 0 , 0 ) (0,0) (0,0),然后走到 ( 1 , 0 ) (1,0) (1,0)

第四头奶牛有两条长度相等的可能路线: ( 1 , 0 ) → ( 0 , 0 ) → ( 0 , 2 ) → ( 1 , 2 ) (1,0)→(0,0)→(0,2)→(1,2) (1,0)(0,0)(0,2)(1,2) ( 1 , 0 ) → ( 2 , 0 ) → ( 2 , 2 ) → ( 1 , 2 ) (1,0)→(2,0)→(2,2)→(1,2) (1,0)(2,0)(2,2)(1,2)


AC_code

python">n,p=map(int,input().split())  
q = []  
for _ in range(p):  x, y = map(int, input().split())  q.append((x, y))  s = [[0] * 1010 for _ in range(1010)]  
sum = 0  
x, y = q[-1]  # 令最后一个柱子的坐标为起点  for i in range(p):  tx, ty = q[i] # 终点  vx = 1 if tx > x else (-1 if tx < x else 0)  vy = 1 if ty > y else (-1 if ty < y else 0)  while x != tx or y != ty:  x += vx  y += vy  sum += 1  s[x][y] = sum  for _ in range(n):  x1, y1, x2, y2 = map(int, input().split())  dis = s[x2][y2] - s[x1][y1]  if dis < 0:  dis += sum  print(min(dis, sum - dis))

END
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢


http://www.ppmy.cn/devtools/167396.html

相关文章

Linux驱动开发实战(五):Qt应用程序点RGB灯(保姆级快速入门!)

Linux驱动开发实战&#xff08;五&#xff09;&#xff1a;Qt应用程序点RGB灯&#xff08;保姆级快速入门&#xff01;&#xff09; 文章目录 Linux驱动开发实战&#xff08;五&#xff09;&#xff1a;Qt应用程序点RGB灯&#xff08;保姆级快速入门&#xff01;&#xff09;前…

【SpringMVC】深入解析使用 Postman 和浏览器模拟将单个与多个参数传递到后端的原理和后端接收参数的过程

SpringMVC—请求(Request) 访问不同的路径&#xff0c;就是发送不同的请求&#xff1b;在发送请求时&#xff0c;可能会带一些参数&#xff0c;所以学习Spring的请求&#xff0c;主要是学习如何传递参数到后端以及后端如何接收&#xff1b; 我们主要是使用 浏览器 和 Postman …

Python :数据模型

一. 什么是数据模型&#xff1f; Python数据模型是Python对象系统的抽象&#xff0c;通过一组特殊方法​&#xff08;如__init__、__len__等&#xff09;和协议​&#xff08;如迭代协议、上下文管理协议&#xff09;&#xff0c;定义了对象如何与语言的内置功能&#xff08;如…

DAY33 贪心算法Ⅱ

122. 买卖股票的最佳时机 II - 力扣&#xff08;LeetCode&#xff09; 想到把整体利润分解为每天的利润&#xff0c;就豁然开朗了。 class Solution { public:int maxProfit(vector<int>& prices) {int result0;for(int i1;i<prices.size();i){resultmax(0,pric…

运行时动态安全—下一代应用防护技术 : 云鲨RASP

代码疫苗内核驱动的新一代应用威胁自免疫平台 Xshark RASP Adaptive Application Protection Platform 云鲨RASP自适应威胁免疫平台通过专利级AI检测引擎、应用漏洞攻击免疫算法、运行时安全切面调度算法及纵深流量学习算法等关键技术&#xff0c;将主动防御能力“注入”到业…

参考thinkphp架构的FastAPI实现思路

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;基于 Python 3.7 并使用了类型提示。虽然 FastAPI 和 ThinkPHP 的设计理念和语言不同&#xff0c;但 FastAPI 同样可以实现 ThinkPHP 的核心功能&#xff0c;如路由、模…

做到哪一步才算精通SQL

做到哪一步才算精通SQL-Structured Query Language 数据定义语言 DDL for StructCREATE&#xff1a;用来创建数据库、表、索引等对象ALTER&#xff1a;用来修改已存在的数据库对象DROP&#xff1a;用来删除整个数据库或者数据库中的表TRUNCATE&#xff1a;用来删除表中所有的行…

从零开始学习机器人---如何高效学习机械原理

如何高效学习机械原理 1. 理解课程的核心概念2. 结合图形和模型学习3. 掌握公式和计算方法4. 理论与实践相结合5. 总结和复习6. 保持好奇心和探索精神 总结 机械原理是一门理论性和实践性都很强的课程&#xff0c;涉及到机械系统的运动、动力传递、机构设计等内容。快速学习机械…