D. Pair Of Lines

Codeforces

IDCF961D

Time2000ms

Memory256MB

Difficulty—

geometry

English · Original

Chinese · Translation

Formal · Original

You are given _n_ points on Cartesian plane. Every point is a lattice point (i. e. both of its coordinates are integers), and all points are distinct. You may draw two straight lines (not necessarily distinct). Is it possible to do this in such a way that every point lies on at least one of these lines? ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 105) — the number of points you are given. Then _n_ lines follow, each line containing two integers _x__i_ and _y__i_ (|_x__i_|, |_y__i_| ≤ 109)— coordinates of _i_\-th point. All _n_ points are distinct. ## Output If it is possible to draw two straight lines in such a way that each of given points belongs to at least one of these lines, print _YES_. Otherwise, print _NO_. [samples] ## Note In the first example it is possible to draw two lines, the one containing the points 1, 3 and 5, and another one containing two remaining points. <center>![image](https://espresso.codeforces.com/dd5a133292f58f4f6d176e1d28e347d46d949a87.png)</center>

给定平面上的 #cf_span[n] 个点。每个点都是格点（即其两个坐标均为整数），且所有点互不相同。你可以画两条直线（不一定不同）。是否可能做到每一点都至少位于其中一条直线上？第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 105)] —— 你被给定的点的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] #cf_span[(|xi|, |yi| ≤ 109)] —— 第 #cf_span[i] 个点的坐标。所有 #cf_span[n] 个点互不相同。如果可以画出两条直线，使得每个给定点都至少属于其中一条直线，则输出 _YES_；否则输出 _NO_。在第一个例子中，可以画出两条直线：一条经过点 #cf_span[1]、#cf_span[3] 和 #cf_span[5]，另一条经过剩下的两个点。 ## Input 第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 105)] —— 你被给定的点的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[xi] 和 #cf_span[yi] #cf_span[(|xi|, |yi| ≤ 109)] —— 第 #cf_span[i] 个点的坐标。所有 #cf_span[n] 个点互不相同。 ## Output 如果可以画出两条直线，使得每个给定点都至少属于其中一条直线，则输出 _YES_；否则输出 _NO_。 [samples] ## Note 在第一个例子中，可以画出两条直线：一条经过点 #cf_span[1]、#cf_span[3] 和 #cf_span[5]，另一条经过剩下的两个点。

**Definitions** Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $. Let $ P = \{ (x_i, y_i) \in \mathbb{Z}^2 \mid i = 1, \dots, n \} $ be a set of $ n $ distinct lattice points. **Objective** Determine whether there exist two lines $ \ell_1, \ell_2 \subseteq \mathbb{R}^2 $ such that: $$ P \subseteq \ell_1 \cup \ell_2 $$ **Constraints** - All points in $ P $ are distinct. - Coordinates satisfy $ |x_i|, |y_i| \leq 10^9 $.

Samples

Input #1

Output #1

YES

Input #2

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Pair Of Lines",
    "description": {
      "content": "You are given _n_ points on Cartesian plane. Every point is a lattice point (i. e. both of its coordinates are integers), and all points are distinct. You may draw two straight lines (not necessarily",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF961D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ points on Cartesian plane. Every point is a lattice point (i. e. both of its coordinates are integers), and all points are distinct.\n\nYou may draw two straight lines (not necessarily...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定平面上的 #cf_span[n] 个点。每个点都是格点（即其两个坐标均为整数），且所有点互不相同。\n\n你可以画两条直线（不一定不同）。是否可能做到每一点都至少位于其中一条直线上？\n\n第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 105)] —— 你被给定的点的数量。\n\n接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[xi] 和 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $.  \nLet $ P = \\{ (x_i, y_i) \\in \\mathbb{Z}^2 \\mid i = 1, \\dots, n \\} $ be a set of $ n $ distinct lattice points.\n\n**Objective**  ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments