← 返回题目列表

AtCoder · ahc039_a

A. 围网捕鱼

中文机器翻译题面 查看原题

故事

高桥是一位熟练的围网渔民。 他的渔船配备了最先进的声纳,使他能够准确确定钓鱼区域内鱼类的位置。 此外,船能够高速移动,使他能够在布设渔网时假设鱼保持静止。

捕鱼方法是用船布网形成一个封闭的多边形,捕获封闭区域内的鱼。 为了优化效率,由网络形成的多边形的每条边必须平行于东西或南北方向对齐。 此外,由于船上配备的网的长度有限,必须在这些限制内构建多边形。

钓鱼区有两种鱼:鲭鱼和沙丁鱼。 出于保护资源的原因,目前禁止在该渔区捕获沙丁鱼。 任何被网捕获的沙丁鱼都必须放回海里。 由于这个过程是劳动密集型的,高桥应该集中精力最大限度地捕获鲭鱼,同时尽可能避免沙丁鱼。

问题陈述

有 N 鲭鱼和 N 二维平面上的沙丁鱼。 构造一个满足以下条件的多边形,并最大化该多边形内的鲭鱼总数减去该多边形内的沙丁鱼总数所得到的值。 请注意,位于多边形边缘上的任何点都被视为位于多边形内部。

条件

  1. 多边形中的顶点数不得超过 1000,其边的总长度不得超过 4 \times 10^5.
  2. 每个顶点的坐标 (x, y) 必须是满足以下条件的整数 0 \leq x, y \leq 10^5.
  3. 多边形的每条边必须平行于 x- 轴或 y- 轴。
  4. 多边形不得自相交:非相邻边不得共享任何点,并且相邻边只能在其端点相交。

评分

让 a 是多边形内鲭鱼的总数, b 是多边形内沙丁鱼的总数。 然后,您将获得的分数 \max(0, a - b + 1).

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

N
x_0 y_0
\vdots
x_{2N-1} y_{2N-1}
  • 在所有测试用例中,鲭鱼和沙丁鱼的数量, N,固定为 5000.
  • 对于每个 i = 0, 1, \dots, N-1, (x_i, y_i) 代表坐标 i-第鲭鱼。
  • 对于每个 i = 0, 1, \dots, N-1, (x_{N+i}, y_{N+i}) 代表坐标 i-第一个沙丁鱼。
  • 各坐标 (x_i, y_i) 满足 0 \leq x_i, y_i \leq 10^5,并且所有坐标都是不同的。

输出

设多边形的顶点数为 m (4 \leq m \leq 1000),并让 (a_i, b_i) 表示坐标 i- 第一个顶点。 然后,按以下格式输出到标准输出:

m
a_0 b_0
\vdots
a_{m-1} b_{m-1}

输出顶点不一定需要形成多边形的实际角。 换句话说,三个连续的顶点 (a_i, b_i), (a_{i+1}, b_{i+1}), (a_{i+2}, b_{i+2}) 可能位于一条直线上。 但是,所有顶点必须具有不同的坐标。

顶点可以按顺时针或逆时针顺序输出。

显示示例

您的程序可能会输出多个解决方案。 如果输出多个解,则仅使用最后一个进行评分。 您可以使用可视化工具的网络版本来比较多个解决方案。

输入生成

  • \mathrm{rand}(L, U): 生成一个均匀分布的随机整数 L 和 U (含)。
  • \mathrm{rand\_double}(L, U): 生成一个均匀分布的随机实数 L 和 U.
  • \mathrm{normal}(\mu, \sigma):从具有均值的正态分布生成随机实数 \mu 和标准差 \sigma.

首先,生成鲭鱼的坐标。 簇数 n 通过生成确定 n = \mathrm{rand}(10, 25)。 对于每个簇 i,生成以下参数:

  • 重量 w_i = \mathrm{rand\_double}(0, 1)
  • 中心 (cx_i, cy_i) = (\mathrm{rand}(20000, 80000), \mathrm{rand}(20000, 80000))
  • 标准差 \sigma_i = \mathrm{rand}(1000, 5000)

重复以下过程 N 次生成坐标 N 鲭鱼:

  • 随机选择一个簇 i 概率与其权重成正比 w_i.
  • 生成 x = \mathrm{round}(\mathrm{normal}(cx_i, \sigma_i)) 和 y = \mathrm{round}(\mathrm{normal}(cy_i, \sigma_i)).
  • 如果生成的坐标 (x, y) 满足 0 \leq x, y \leq 10^5 并且与所有先前生成的坐标不同,它们被接受为鲭鱼的坐标。否则,重新生成 (x, y).

生成鲭鱼的坐标后,以同样的方式生成沙丁鱼的坐标。

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。