QOJ.ac

QOJ

حد الوقت: 4.0 s حد الذاكرة: 256 MB مجموع النقاط: 100 قابلة للهجوم ✓

#14106. 生日蛋糕

الإحصائيات

太令人兴奋了!今天是你的小弟弟的生日!为此你订购了一个巨大的 $(1 \times 1)$ 米的蛋糕。

这是一个特殊的香草蛋糕,上面有 $n$ 个甜甜的巧克力豆和 $m$ 个清爽的草莓。

你向他展示了你准备的巨大惊喜,然而……真糟糕!原来他讨厌水果!“当然,我怎么能忘记呢?”你说道。尽管如此,他非常喜欢吃巧克力,所以如果你能切给他一块不含任何草莓的蛋糕,他会很高兴。为了让他开心,你想给他一块含有尽可能多巧克力豆的蛋糕。

上图描绘了样例测试数据。

你只能沿着一条直线对蛋糕进行一次切割,并且不允许切到任何巧克力豆或草莓。你最多可以给你的弟弟多少个巧克力豆?

注意:上图仅用于说明目的。你应该将巧克力豆和草莓都视为无限小(即点)。

输入格式

输入的第一行包含两个正整数 $n$ ($1 \le n \le 50\,000$) 和 $m$ ($1 \le m \le 100$) —— 分别表示巧克力豆和草莓的数量。

接下来的 $n + m$ 行中的第 $i$ 行包含两个小数 $x_i$ 和 $y_i$ ($0 < x_i, y_i < 1$),表示第 $i$ 个配料的坐标:前 $n$ 个配料是巧克力豆,剩下的 $m$ 个是草莓。

所有数字最多给出 6 位小数。所有 $n + m$ 个配料的位置都是互不相同的。

输出格式

输出一个非负整数 $c$,表示在对蛋糕进行恰好一次切割后,你最多可以给你的弟弟多少个巧克力豆。

样例

输入样例 1

5 2
0.2 0.6
0.8 0.6
0.6 0.2
0.1 0.2
0.6 0.8
0.6 0.6
0.5 0.5

输出样例 1

3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.