2018年8月9日 2020年8月3日 Wong, LimstashOI, 数学, 贪心
1 JZOJ - 3493 三角形
JZOJ - 3493 三角形
平面上有 $n$ 个点,求出用这些点可以构成的三角形数.
第一行一个整数 $n$ .
接下来 $n$ 行,每行两个整数,表示点的坐标.
输出仅一个整数,表示所求答案.
对于 50% 的数据,n <= 300.
对于 100% 的数据,n <= 3000 ,坐标的绝对值不超过 10^4 ,保证没有重合的点.
暴力解法:枚举三个点,判断这三个点是否在同一条直线上,如果再同一条直线上则不能构成三角形.
思考如何判断三个点是否在同一直线上.
我们可以通过计算斜率的方式判