传统题 1000ms 256MiB

数三角形

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

作为一名学霸,当然要学会数数,不仅要会数正方体,也要会数三角形。

在二维平面上存在位置互不相同的 nn 个点,这些点的横纵坐标均为整数,第 ii 个点的坐标为 (ai,bi)(a_i,b_i)。你需要计算存在多少个三元组 (i,j,k)(1i<j<kn)(i,j,k)(1≤i<j<k≤n) 满足 i,j,ki,j,k 三个点可以构成面积大于 00 的等腰三角形。

当然了,为了简化一些计算量,本题还满足一个特殊性质:这 nn 个点仅存在于两条距离不超过 1010 的平行于 x 轴的直线上。

输入格式

第一行输入一个正整数 n,x,y(1n105,0x<y10)n,x,y(1≤n≤10^5,0≤x<y≤10) 表示点的个数,两条平行于 x 轴的直线的纵坐标。

接下来 nn 行,每行两个正整数 ai,bi(0ai105,bix,y)a_i,b_i (0≤a_i≤10^5,b_i ∈{x,y}) 表示第 ii 个点的坐标,数据保证没有两个点重合的情况。

输出格式

一行一个正整数表示三元组的个数,答案可能很大,需要对 998244353998244353 取模。

6 3 5
0 3
0 5
1 3
1 5
2 3
2 5
6
4 5 9
5 5
8 9
13 9
3 9
2

解释 #2

两个等腰三角形为 ΔABDΔABDΔABCΔABC

第八届中国大学生程序设计竞赛高职专场

未参加
状态
已结束
规则
XCPC
题目
12
开始于
2022-10-23 9:00
结束于
2022-10-23 14:00
持续时间
5 小时
主持人
参赛人数
1