seuOJ493 - 美丽角对

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：Div.1, 2024

题目描述

一对不同的角为美丽角对当且仅当：$gcd(\theta_{i},\theta_{j})=1$ ，其中 $\theta$ 是角的角度值向下取整的值，例如 $60.4°=60$。

规定 $gcd(0,\theta)=\theta$，且 $180°$ 的角的顶点不能算作凸包的顶点。

给定 $n$ 个点的坐标 $(x,y)$ ，问最大凸包的美丽角对一共有多少对，重复的角对无需计算（即假如角对 $i,j$ 已经被计算，那么无需再计算角对 $j,i$）。

最大凸包即含所有的点，并且所有的点都在凸多边形的边界上或内部的凸多边形。

输入格式

第一行输入整数 $n$ $(3 \le n \le 10^5)$ ，表示点的数量；

后面 $n$ 行中，每行输入两个整数 $x,y(0 \le x,y \le 10^9)$，表示点的坐标，保证所有给出的点的坐标互不相同。

保证给出的所有的点一定可以构成至少一个凸包。

输出格式

输出美丽角对的数量。

样例

输入样例1

9
1 2
3 1
1 5
2 9
3 2
3 7
4 2
6 3
2 1

输出样例1

8

输入样例2

4
0 0
0 1
1 1
1 0

输出样例2

0

输入样例3

8
0 0
0 1
0 2
0 3
1 3
2 3
3 3
4 3

输出样例3

2

提示
样例 $1$ 如下：