← 返回题目列表

AtCoder · ahc001_a

A. AtCoder 广告

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

问题陈述

AtCoder 已决定投放网络广告 n 公司位于首页。 放置广告的空间是尺寸为10000×10000的正方形。 每个公司的空间必须是一个面积为正的与轴平行的矩形,并且顶点坐标必须是整数值。 不同的矩形的边可以接触,但不能重叠。换句话说,公共区域不得有正面积。 允许留出一些不属于任何广告的可用空间。

高桥社长向各公司询问了他们想要的位置和区域。公司简介 i 想要一个具有面积的广告空间 r_i 包括点 (x_i+0.5, y_i+0.5)。 满意度水平 公司 p_i 公司的 i 确定如下。

  • 如果公司的广告空间 i 不包含该点 (x_i+0.5, y_i+0.5),那么 p_i = 0.
  • 如果公司的广告空间 i 包含点 (x_i+0.5, y_i+0.5) 面积为 s_i,那么 p_i = 1 - (1 - \min(r_i,s_i) / \max(r_i, s_i))^2.

您的任务是确定广告的展示位置,以使满意度的总和最大化。 您将获得以下分数 10^9 \times \sum_{i=0}^{n-1} p_i / n 四舍五入到最接近的整数。


输入

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

n
x_0 y_0 r_0
\vdots
x_{n-1} y_{n-1} r_{n-1}
  • 50\leq n\leq 200
  • x_i 和 y_i 是满足以下条件的整数 0\leq x_i\leq 9999 和 0\leq y_i\leq 9999。对于任何 i\neq j, (x_i,y_i)\neq (x_j,y_j) 成立。
  • r_i 是至少为 1 的整数并且满足 \sum_{i=0}^{n-1} r_i=10000\times 10000.

输出

让 (a_i, b_i) 和 (c_i, d_i) (0\leq a_i<c_i\leq 10000, 0\leq b_i<d_i\leq 10000) 是代表公司广告空间的矩形的两个对角顶点的坐标 i。 按以下格式输出到标准输出。

a_0 b_0 c_0 d_0
\vdots
a_{n-1} b_{n-1} c_{n-1} d_{n-1}

输入生成

让 rand() 是生成至少零且小于一的均匀随机双精度浮点数的函数。

的一代 n

企业数量 n 通过舍入生成 50 × 4^{rand()} 到最接近的整数值。

的一代 x_i 和 y_i

所需位置列表 (x_1,y_i),\ldots,(x_n,y_n) 是通过随机抽样生成的 n 不同的坐标 \{(x, y) \mid x\in \{0,1,\ldots,9999\}, y\in\{0,1,\ldots,9999\}\}.

的一代 r_i

让 q_1,\ldots,q_{n-1} 是一个排序列表 n-1 随机采样的不同整数 \{1,2,\ldots,99999999\}。 让 q_0=0 和 q_n=100000000。 然后 r_i=q_{i+1}-q_i.

测试用例数量

  • 临时测试:50
  • 系统测试:1000。我们将发布 种子.txt (md5=8fc1ce3f4beabac6abc1bdb4206d7f7e) 比赛结束后。

提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判定为WA或TLE,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。

工具

您可以下载输入生成器和可视化工具 这里。 要使用它们,您需要一个编译环境 Rust 语言. 感谢 kenkoooo,您现在可以使用网络上的工具,尽管它们并未得到官方支持。 https://kenkoooo.github.io/ahc001-gen-vis-wasm/


示例输入 1

50
1909 360 6468907
5810 7091 4661329
5407 422 2010076
5767 3140 681477
6659 3234 920591
4206 1620 2487369
7853 9492 440133
7875 432 586159
9048 5059 1805425
7292 9070 509242
7633 2496 1558444
421 4835 1808752
7164 4109 35081
5356 2271 78438
5261 577 971398
3546 5225 1871979
4667 3386 28796
5596 7896 3310195
2518 9813 1739130
9002 3913 334620
8574 8947 1107057
3118 1773 669849
7140 4388 2098247
8544 8196 1742491
8577 4337 4435283
3155 9168 976005
7823 4404 945830
9451 110 569854
7031 1389 787729
1841 2337 942236
76 8364 710110
3543 3931 3840994
3927 8828 2920828
5671 3305 1526349
5542 4587 6285390
4030 7732 3962404
8575 8200 3662259
1139 3739 254000
50 7415 647735
934 4056 1800657
8801 7178 1218595
4499 6207 660560
3096 3375 2695827
5252 3281 1046149
2247 1446 7148429
3347 8501 7546190
5791 8600 3909497
8033 8992 3365971
2297 9254 23830
4312 6176 192104

示例输出 1

0 0 4473 1446
4634 5915 6987 7896
4473 0 7875 577
5260 2633 6274 3305
6274 2722 7172 3747
3174 1446 5238 2651
7522 9161 8185 9824
7875 0 8454 1012
8376 4388 9720 5731
6890 8668 7522 9473
7172 1815 8315 3178
0 4072 1185 5598
7071 4016 7258 4203
5238 2124 5504 2418
4565 577 5958 1274
2862 4541 4230 5909
4582 3302 4752 3471
3348 7896 8049 8600
1351 9255 3685 10000
8713 3624 9291 4202
8185 8373 9149 9521
2480 1446 3174 2411
6105 4203 7823 5424
8049 5731 8575 8373
7823 3178 8713 4388
2410 8600 3900 9255
7823 4388 8376 5731
8969 0 9933 591
6581 940 7481 1815
1356 1852 2327 2822
0 7805 635 8923
1286 3376 4582 4541
3900 8600 5791 10000
4752 3305 6274 4203
4582 4203 6105 5915
2287 6208 4634 7896
8575 7179 10000 8373
849 3449 1286 4030
0 6812 652 7805
0 4030 1286 4072
8575 6182 9797 7179
4313 5915 4634 6208
2327 2651 4582 3376
4752 2651 5260 3305
0 1446 2480 1852
635 7896 3348 8600
5791 8600 6890 10000
7522 8600 8185 9161
2188 9146 2406 9255
3671 5909 4313 6208