注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "goat.h"。

题目描述

题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2 「염소」

在广阔的平原上有 $N$ 头山羊悠闲地吃草。没有两个或以上的山羊在同一位置。山羊们很懒惰，不会移动位置，只会在原地转圈。实际上，这些山羊都是机器人，只能在原地旋转。此外，山羊的鼻子上有 LED 灯，可以远程点亮。山羊的眼睛是高性能摄像头，可以实时远程查看摄像头捕获的图像，并可以保存想要的场景。山羊的眼睛可以看到自己的鼻子，也有透视功能，即使山羊重叠也能知道有多少只。山羊的左右视野为 $180^{\circ}$，在 $180^{\circ}$ 边界上的物体也能看见。

根据山羊的位置，有些山羊可以一次看到 $N$ 头山羊，而有些山羊无论朝哪个方向看都无法一次看到 $N$ 头山羊。例如，下面的图中，编号为 $0$ 到 $5$ 的六只山羊中，$5$ 号山羊可以一次看到六只山羊，但 $2$ 号山羊无论朝哪个方向看都无法一次看到六只山羊。

为了进行特殊的实验，我们选择两只一次能看到 $N$ 头山羊的不同山羊，再从剩下的山羊中任意选择一只。这三只选定的山羊将点亮鼻子，以便随时确认它们的位置。观察选定三只山羊眼中捕获到的图像，并在每只山羊能看到点亮的三只山羊同框的场景下各自保存一张图像。然后，逐一查看保存的三张图像，对每张图像中点亮的两只其他山羊之间（包括边界）可见的所有山羊进行特殊标记。这个标记是为了特殊的实验，实验的目标是统计 $N$ 只山羊中被标记了三次的山羊数量。

例如，如果在全部六只山羊中选定的三只山羊用红点表示，下面的图显示了以每只山羊为基准被特殊标记的山羊。（当然，每张图并非是保存的场景本身。）在这种情况下，被标记了三次的山羊数量是 $4$。

你需要为这个特殊的实验实现以下两个函数：

• void init(int x[], int y[]);
  最初被调用，并且只调用一次。x 和 y 是大小为 $N$ 的数组（向量）。x[0..N-1] 表示山羊的 $x$ 坐标，y[0..N-1] 表示山羊的 $y$ 坐标。编号为 i $(0 \leq i \leq N-1)$ 的山羊位置是 (x[i], y[i])。

• int count(int a, int b, int c);
  使用给定的三只山羊的坐标 (x[a], y[a])，(x[b], y[b])，(x[c], y[c])，计算被标记了三次的山羊数量并返回。

实现细节

你需要提交一个名为 goat.cpp 的文件。该文件必须实现以下函数：

• void init(int x[], int y[]);
• int count(int a, int b, int c);

这些函数必须按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不得进行输入输出操作或访问其他文件。

示例评测程序

示例评测程序以以下格式读取输入：

• 第 $1$ 行：$N\, Q$，其中 $N$ 表示山羊的数量，$Q$ 表示查询的数量
• 接下来的 $N$ 行：每行两个整数 $x\, y$，表示山羊位置的 $x$ 坐标和 $y$ 坐标
• 接下来的 $Q$ 行：每行三个整数 $a\,b\,c$ $(0 \leq a, b, c \leq N-1)$，表示三只山羊的编号

示例评测程序对每个查询输出一行一个整数，表示满足条件的山羊数量。

6 3
0 0
1 1
2 2
4 3
0 2
2 0
0 5 2
1 3 4
4 1 5

4
4
3

下面是样例 1 的函数调用及其结果：

函数调用	返回值
init({0, 1, 2, 4, 0, 2}, {0, 1, 2, 3, 2, 0})	4
count(0, 5, 2)	4
count(1, 3, 4)	3
count(4, 1, 5)

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 3\,000$
• $1 \leq Q \leq 5 \times 10^{6}$
• 所有山羊的 $x$ 坐标和 $y$ 坐标都在 $0$ 到 $10^{9}$ 之间

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	$N \leq 500, Q \leq 10^{5}$；任何三点不在一条直线上
$2$	$17$	$N \leq 500, Q \leq 10^{5}$
$3$	$10$	$N \leq 500$；任何三点不在一条直线上
$4$	$8$	$N \leq 500$
$5$	$29$	任何三点不在一条直线上
$6$	$31$	无附加限制