atcoder#AGC051B. [AGC051B] Bowling

[AGC051B] Bowling

题目描述

平面上にボウリングのピンが何本か立っており、それを 4 4 人の人が異なる角度から眺めています。 1 1 人にだけ他の人より遥かに多くのピンが見えることはあるでしょうか。

ピンを単純に xy xy 平面上の点集合とみなしましょう。 4 4 人の位置を以下の図に示します。 厳密には、

  • A さんから見ると、y y 座標が等しい 2 2 本のピンは重なって見えます。
  • B さんから見ると、(x x 座標 - y y 座標) が等しい 2 2 本のピンは重なって見えます。
  • C さんから見ると、x x 座標が等しい 2 2 本のピンは重なって見えます。
  • D さんから見ると、(x x 座標 + y y 座標) が等しい 2 2 本のピンは重なって見えます。

A, B, C, D さんに見えるピンの数をそれぞれ a, b, c, d a,\ b,\ c,\ d とします。

以下の条件を全て満たすような何らかのピンの配置を構成してください。

  • d  10  max { a, b, c } d\ \geq\ 10\ \cdot\ \max\ \{\ a,\ b,\ c\ \}
  • ピンの本数は 1 1 本以上 105 10^5 本以下である。
  • ピンの座標は全て 0 0 以上 109 10^9 以下の整数である。
  • 2 2 本のピンが同じ位置にあることはない。

输入格式

入力はない。

输出格式

答えを以下の形式で出力せよ。ここで、N N はピンの本数、(xi, yi) (x_i,\ y_i) i i 本目のピンの座標である。

N N x1 x_1 y1 y_1 : : xN x_N yN y_N

出力は、問題文中の条件を満たすものでなければならない。

题目大意

有数个大头钉在二维平面上,有四个人从不同的角度观察它们,重叠的点视为一个,是否可能有一个人观察到的大头钉数量远多余其他人?

让我们把大头钉的位置简化为二维坐标上的点。四个人观察的角度如下:

  • A 从左往右观察。即所有 yy 坐标相同的点是重叠的。
  • B 从左下往右上观察。即所有 xx 坐标与 yy 坐标相减的值相同的点是重叠的。
  • C 从下往上观察。即所有 xx 坐标相同的点是重叠的。
  • D 从右下往左上观察。即所有 xx 坐标与 yy 坐标相加的值相同的点是重叠的。

A, B, C, D 观察到的大头针数量为 a,b,c,da, b, c, d,你需要构造一组大头针的排布,满足以下一些条件:

  • d10×max{a,b,c}d \geq 10 \times \max\{a, b, c\}
  • 大头钉的数量不多于 10510^5 个。
  • 大头钉的坐标均为 [0,109][0, 10^9] 内的整数。
  • 不存在两个坐标相同的大头钉。

没有输入,直接输出一组解。


9
1 1
1 5
2 7
4 4
5 3
6 8
7 5
8 2
8 7

提示

Sample Explanation 1

**この出力例は出力形式を例示するものであり、正解ではありません。** この出力は問題文中の図に対応し、d = 8, a = b = c = 7 d\ =\ 8,\ a\ =\ b\ =\ c\ =\ 7 です。頑張りましたが、AC には届きません。