acwing-2983. 玩具(计算几何)

acwing-2983. 玩具(计算几何)计算玩具收纳盒中,每个分区内的玩具数量。约翰的父母有一个烦恼—-约翰每次玩完玩具以后总会将玩具乱扔。他们为约翰准备了一个长方形的玩具收纳盒,用来放他的玩具。但是约翰非常调皮,每次都非常随意的将玩具扔进盒子中,使得所有玩具都随意混在一起,这让约翰难以找到他喜欢的玩具。对此,约翰的父母想出了一个对策,用若干个纸板将收纳盒分隔成若干个分区,这样至少扔到不同分区的玩具之间还是能分开的。下面是一个收纳盒的俯视图示例。1.jpg你的任务是,每当约翰将玩具扔进收纳盒中时,确定每个分区中有多少个玩具。输

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

计算玩具收纳盒中,每个分区内的玩具数量。

约翰的父母有一个烦恼—-约翰每次玩完玩具以后总会将玩具乱扔。

他们为约翰准备了一个长方形的玩具收纳盒,用来放他的玩具。

但是约翰非常调皮,每次都非常随意的将玩具扔进盒子中,使得所有玩具都随意混在一起,这让约翰难以找到他喜欢的玩具。

对此,约翰的父母想出了一个对策,用若干个纸板将收纳盒分隔成若干个分区,这样至少扔到不同分区的玩具之间还是能分开的。

下面是一个收纳盒的俯视图示例。

1.jpg

你的任务是,每当约翰将玩具扔进收纳盒中时,确定每个分区中有多少个玩具。

输入格式
本题包含多组测试数据。

对于每组数据,第一行包含 6 个整数 n,m,x1,y1,x2,y2,表示共有 n 个纸板,m 个玩具,收纳盒的左上角坐标为 (x1,y1),右下角坐标为 (x2,y2)。

接下来 n 行,每行包含两个整数 Ui,Li,表示第 i 个纸板的两端点坐标分别为 (Ui,y1) 和 (Li,y2)。数据保证纸板之间不相交,且按照从左至右顺序依次给出。

接下来 m 行,每行包含两个整数 Xj,Yj,表示第 j 个玩具的位置坐标。玩具的给出顺序是随机的。数据保证玩具不会恰好落在纸板上,也不会落在盒子外。

输入由包含单个 0 的一行结束。

输出格式
对于每组数据,输出 n+1 行。

n 个纸板将收纳盒划分为了 n+1 个分区,从左到右编号为 0∼n。

按照分区编号从小到大的顺序,每行输出一行信息 i: j,其中 i 表示分区编号,j 表示分区内玩具数量。

每组数据之间,用空行隔开。

数据范围
每个测试点最多包含 10 组数据。
1≤n,m≤5000,
所有坐标取值范围 [−105,105]。

输入样例:
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0
输出样例:
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

注意
如示例所示,落在盒子边缘的玩具也算在盒子内。
题解
二分+点与直线位置关系

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168614.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 一元线性回归方程公式_用普通最小二乘法估计经典线性模型

    一元线性回归方程公式_用普通最小二乘法估计经典线性模型概述别看公式多,其实很简单最小二乘法其实又叫最小平方法,是一种数据拟合的优化技术。实质上是利用最小误差的平方寻求数据的最佳匹配函数,利用最小二乘法可以便捷的求得未知的数据,起到预测的作用,并且是的这些预测的数据与实际数据之间的误差平方和达到最小。一般应用在曲线拟合的目的上。原理本篇文章不考虑其他方面的应用,我们用最简单的实例说明最小二乘法的工作原理与其内在含义。当我们在研究两个…

  • 【算法题】单例模式的8种实现方式(java版)「建议收藏」

    【算法题】单例模式的8种实现方式(java版)「建议收藏」根据马士兵老师的视频整理下来的8种单例模式的实现方式,在此记录一下。代码示例1:饿汉式packagecom.examples.singleton;publicclassMgr01{publicstaticvoidmain(String[]args){Mgr01m1=Mgr01.getInstance();Mgr01m2=Mgr01.getInstance();System.out.println(m1…

  • 计算机发展史资料简介,计算机发展史简介「建议收藏」

    计算机发展史资料简介,计算机发展史简介「建议收藏」人类所使用的计算工具是随着生产的发展和社会的进步,有着从简单到复杂、从低级到高级的发展过程,计算工具相继出现了如算盘、计算尺、手摇机械计算机、电动机械计算机等。1946年,世界上第一台电子数字计算机(ENIAC)在美国诞生。这台计算机共用了18000多个电子管组成,占地170m2,总重量为30t,耗电140kw,速度达到每秒能进行5000次加法、300次乘法运算。电子计算机在短短的50多年里经过了…

    2022年10月18日
  • C++ vector 初始化大小[通俗易懂]

    C++ vector 初始化大小[通俗易懂]一维数组使用下面的代码可以初始化一个大小为n的一维数组vector<int>dp(n);二维数组使用下面的代码可以初始化一个row行col列的二维数组vector<vector<int>>dp(row,vector<int>(col));三维数组使用下面的代码可以初始化一个三维数组,维度分别为n1,n2,n3vector<vector<vector<int>>>dp(n1,vector&

  • scope 前缀开头的方法

    scope 前缀开头的方法

  • Python装饰器高级用法

    Python装饰器高级用法

    2020年11月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号