F. Disjoint Triangles

Codeforces

IDCF1025F

Time2000ms

Memory256MB

Difficulty—

geometry

English · Original

Chinese · Translation

Formal · Original

A point _belongs_ to a triangle if it lies inside the triangle or on one of its sides. Two triangles are _disjoint_ if there is no point on the plane that belongs to both triangles. You are given $n$ points on the plane. No two points coincide and no three points are collinear. Find the number of different ways to choose two disjoint triangles with vertices in the given points. Two ways which differ only in order of triangles or in order of vertices inside triangles are considered equal. ## Input The first line of the input contains an integer $n$ ($6 \le n \le 2000$) – the number of points. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10^9$) – the coordinates of a point. No two points coincide and no three points are collinear. ## Output Print one integer – the number of ways to choose two disjoint triangles. [samples] ## Note In the first example there are six pairs of disjoint triangles, they are shown on the picture below. <center>![image](https://espresso.codeforces.com/52cd4121e68d9af086bf6dae99167b17720344bc.png)</center>All other pairs of triangles are not disjoint, for example the following pair: <center>![image](https://espresso.codeforces.com/2a0ebd7fb7f5c07f791dcf28da627bdf8406dab3.png)</center>

一个点属于一个三角形，当且仅当它位于三角形内部或其某条边上。两个三角形是互不相交的，当且仅当平面上不存在任何点同时属于这两个三角形。给定平面上的 $n$ 个点。任意两点不重合，且任意三点不共线。求有多少种不同的方式，从给定点中选出两个互不相交的三角形（三角形的顶点均来自这些点）。两种方式若仅在三角形的顺序或三角形内顶点的顺序上不同，则视为相同。输入的第一行包含一个整数 $n$（$6 lt.eq n lt.eq 2000$）——点的数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$| x_i |, | y_i | lt.eq 10^9$）——一个点的坐标。任意两点不重合，且任意三点不共线。请输出一个整数——选出两个互不相交三角形的方法数。在第一个示例中，有六对互不相交的三角形，如下面的图所示。所有其他三角形对都不是互不相交的，例如以下这一对： ## Input 输入的第一行包含一个整数 $n$（$6 lt.eq n lt.eq 2000$）——点的数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$| x_i |, | y_i | lt.eq 10^9$）——一个点的坐标。任意两点不重合，且任意三点不共线。 ## Output 请输出一个整数——选出两个互不相交三角形的方法数。 [samples] ## Note 在第一个示例中，有六对互不相交的三角形，如下面的图所示。所有其他三角形对都不是互不相交的，例如以下这一对：

**Definitions** Let $ P = \{p_1, p_2, \dots, p_n\} $ be a set of $ n $ distinct points in $ \mathbb{R}^2 $, with no three collinear. Let $ \mathcal{T} $ denote the set of all triangles formed by choosing 3 distinct points from $ P $: $$ \mathcal{T} = \left\{ \{p_i, p_j, p_k\} \subseteq P \mid i < j < k \right\} $$ Let $ \mathcal{D} \subseteq \mathcal{T} \times \mathcal{T} $ be the set of unordered pairs of distinct triangles $ (T_1, T_2) $ such that $ T_1 \cap T_2 = \emptyset $, where $ T_1 \cap T_2 = \emptyset $ means the two triangles are disjoint (no point in the plane belongs to both triangles, including boundaries). **Constraints** 1. $ 6 \leq n \leq 2000 $ 2. All points in $ P $ are distinct. 3. No three points in $ P $ are collinear. **Objective** Compute the number of unordered pairs $ \{T_1, T_2\} $ such that: - $ T_1, T_2 \in \mathcal{T} $, - $ T_1 \ne T_2 $, - $ T_1 \cap T_2 = \emptyset $ (the triangles are disjoint). That is, compute: $$ \left| \left\{ \{T_1, T_2\} \subseteq \mathcal{T} \mid T_1 \ne T_2,\ T_1 \cap T_2 = \emptyset \right\} \right| $$

Samples

Input #1

Output #1

Input #2

7
0 -1000000000
-5 -5
5 -5
-5 0
5 0
-2 2
2 2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Disjoint Triangles",
    "description": {
      "content": "A point _belongs_ to a triangle if it lies inside the triangle or on one of its sides. Two triangles are _disjoint_ if there is no point on the plane that belongs to both triangles. You are given $n$",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1025F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A point _belongs_ to a triangle if it lies inside the triangle or on one of its sides. Two triangles are _disjoint_ if there is no point on the plane that belongs to both triangles.\n\nYou are given $n$...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个点属于一个三角形，当且仅当它位于三角形内部或其某条边上。两个三角形是互不相交的，当且仅当平面上不存在任何点同时属于这两个三角形。\n\n给定平面上的 $n$ 个点。任意两点不重合，且任意三点不共线。\n\n求有多少种不同的方式，从给定点中选出两个互不相交的三角形（三角形的顶点均来自这些点）。两种方式若仅在三角形的顺序或三角形内顶点的顺序上不同，则视为相同。\n\n输入的第一行包含一个整数 $n$（$6 l...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be a set of $ n $ distinct points in $ \\mathbb{R}^2 $, with no three collinear.\n\nLet $ \\mathcal{T} $ denote the set of all triangles formed by ch...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments