问题陈述
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