E. Disjoint Triangles

Codeforces

IDCF951E

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 $ (i.e., the triangles are disjoint: no point in common and their convex hulls do not intersect). **Constraints** 1. $ 6 \le n \le 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\} \subseteq \mathcal{T} $ such that: - $ T_1 \ne T_2 $, - $ T_1 \cap T_2 = \emptyset $ (no shared vertices), - The convex hulls of $ T_1 $ and $ T_2 $ are disjoint (no point of the plane belongs to both triangles). That is, compute: $$ \left| \left\{ \{T_1, T_2\} \subseteq \mathcal{T} \,\middle|\, T_1 \ne T_2,\; T_1 \cap T_2 = \emptyset,\; \text{conv}(T_1) \cap \text{conv}(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": "E. 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": "CF951E"
  },
  "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 lt.eq n lt.eq 2000$）—...",
      "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