B. Parallelogram is Back

Codeforces
IDCF749B
Time1000ms
Memory256MB
Difficulty
brute forceconstructive algorithmsgeometry
English · Original
Chinese · Translation
Formal · Original
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal. Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points. ## Input The input consists of three lines, each containing a pair of integer coordinates _x__i_ and _y__i_ ( - 1000 ≤ _x__i_, _y__i_ ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide. ## Output First print integer _k_ — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices. Then print _k_ lines, each containing a pair of integer — possible coordinates of the fourth point. [samples] ## Note If you need clarification of what parallelogram is, please check Wikipedia page: https://en.wikipedia.org/wiki/Parallelogram
很久以前,Alex 创建了一个关于平行四边形的有趣问题。该问题的输入数据包含笛卡尔平面上的四个整数点,这些点定义了一个非退化(正面积)平行四边形的顶点集合。这些点不一定按顺时针或逆时针顺序给出。 Alex 为这个问题准备了一个非常好的测试用例,但不知怎的,输入的最后一行丢失了,现在他只剩下原始平行四边形的三个点。他记得这个测试用例非常优秀,因此他请你仅根据这三个点恢复第四个点。 输入由三行组成,每行包含一对整数坐标 #cf_span[xi] 和 #cf_span[yi](#cf_span[ - 1000 ≤ xi, yi ≤ 1000])。保证这三个点不共线,且任意两点不重合。 首先输出整数 #cf_span[k] —— 添加一个新整数点,使得所得点集构成某个正面积平行四边形的顶点集合的方法数。点的排列顺序没有特殊要求(如遍历顺序),它们仅定义顶点集合。 然后输出 #cf_span[k] 行,每行包含一对整数 —— 第四个点的可能坐标。 ## Input 输入由三行组成,每行包含一对整数坐标 #cf_span[xi] 和 #cf_span[yi](#cf_span[ - 1000 ≤ xi, yi ≤ 1000])。保证这三个点不共线,且任意两点不重合。 ## Output 首先输出整数 #cf_span[k] —— 添加一个新整数点,使得所得点集构成某个正面积平行四边形的顶点集合的方法数。点的排列顺序没有特殊要求(如遍历顺序),它们仅定义顶点集合。然后输出 #cf_span[k] 行,每行包含一对整数 —— 第四个点的可能坐标。 [samples] ## Note 如果你需要平行四边形的定义说明,请查阅维基百科页面: https://en.wikipedia.org/wiki/Parallelogram
**Definitions** Let $ P_1 = (x_1, y_1) $, $ P_2 = (x_2, y_2) $, $ P_3 = (x_3, y_3) $ be three distinct non-collinear points in $ \mathbb{Z}^2 $. **Constraints** 1. $ -1000 \leq x_i, y_i \leq 1000 $ for $ i \in \{1,2,3\} $ 2. The three points are not collinear. 3. No two points coincide. **Objective** Find all points $ P_4 = (x_4, y_4) \in \mathbb{Z}^2 $ such that the quadrilateral with vertices $ \{P_1, P_2, P_3, P_4\} $ forms a non-degenerate parallelogram. In a parallelogram, the diagonals bisect each other. Thus, for any pair of points as a diagonal, the fourth point is determined by the vector sum: - If $ P_1 $ and $ P_2 $ are endpoints of one diagonal, then $ P_4 = P_3 + (P_1 - P_2) $ - If $ P_1 $ and $ P_3 $ are endpoints of one diagonal, then $ P_4 = P_2 + (P_1 - P_3) $ - If $ P_2 $ and $ P_3 $ are endpoints of one diagonal, then $ P_4 = P_1 + (P_2 - P_3) $ Equivalently, the three possible fourth points are: $$ P_4^{(1)} = P_1 + P_2 - P_3, \quad P_4^{(2)} = P_1 + P_3 - P_2, \quad P_4^{(3)} = P_2 + P_3 - P_1 $$ Let $ S = \{ P_4^{(1)}, P_4^{(2)}, P_4^{(3)} \} $. Since the three given points are not collinear, all three candidates yield non-degenerate parallelograms. However, duplicates may occur only if two expressions yield the same point — but under the given constraints, this is impossible (as the points are distinct and non-collinear). Thus, $ k = 3 $, and the three possible fourth points are: $$ (x_1 + x_2 - x_3,\ y_1 + y_2 - y_3), \quad (x_1 + x_3 - x_2,\ y_1 + y_3 - y_2), \quad (x_2 + x_3 - x_1,\ y_2 + y_3 - y_1) $$
Samples
Input #1
0 0
1 0
0 1
Output #1
3
1 -1
-1 1
1 1
API Response (JSON)
{
  "problem": {
    "name": "B. Parallelogram is Back",
    "description": {
      "content": "Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some no",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF749B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some no...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "很久以前,Alex 创建了一个关于平行四边形的有趣问题。该问题的输入数据包含笛卡尔平面上的四个整数点,这些点定义了一个非退化(正面积)平行四边形的顶点集合。这些点不一定按顺时针或逆时针顺序给出。\n\nAlex 为这个问题准备了一个非常好的测试用例,但不知怎的,输入的最后一行丢失了,现在他只剩下原始平行四边形的三个点。他记得这个测试用例非常优秀,因此他请你仅根据这三个点恢复第四个点。\n\n输入由三行组成...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P_1 = (x_1, y_1) $, $ P_2 = (x_2, y_2) $, $ P_3 = (x_3, y_3) $ be three distinct non-collinear points in $ \\mathbb{Z}^2 $.\n\n**Constraints**  \n1. $ -1000 \\leq x_i, y_i \\leq 1000...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments