#P18765. Captain Thrawn
Captain Thrawn
Captain Thrawn
题目描述
奇斯统治领的索龙上校(Captain Thrawn)被困在帕塔图斯人的母星。他必须把一条重要信息传给阿拉兰尼上将,又等不及友方星舰前来接应,因此需要架设一套由三个部件组成的通信三联装置。三个部件之间的欧几里得距离必须两两相等且非零,也就是放在一个等边三角形的三个顶点上。
由于双方关系紧张,帕塔图斯政府不允许他随意放置装置。帕塔图斯首都是一个边长为 的正六边形,城中道路布局如下。
- 有 条等间距、相互平行、由西向东的街道(street),从南到北编号为 。街道 与正六边形最南边重合,街道 与最北边重合,街道 经过中心。
- 有 条等间距、相互平行、由西北向东南的大道(avenue),从西南到东北编号为 。大道 与正六边形的西南边重合,大道 与东北边重合,大道 经过中心。
- 还有 条等间距、相互平行、由西南向东北的林荫道(boulevard),从东南到西北编号为 。林荫道 与正六边形的东南边重合,林荫道 与西北边重合,林荫道 经过中心。
下图是 时的城市布局(保留原图的英文道路标注):

每个街道、大道与林荫道的交点都有一座塔。如果经过该塔的街道编号为 、大道编号为 、林荫道编号为 ,则称塔的坐标为 。每座塔都属于某位帕塔图斯官员。
有些官员曾得到索龙的帮助,愿意让他把装置部件放在自己的塔上。他们一共拥有 座可用的塔。索龙需要从中选出三座,使它们两两距离相等,从而架设通信装置。
请计算可以选择这三座塔的方案数。选取的三座塔必须互不相同,三角形边长必须非零;同一组塔不因选取顺序不同而重复计数。
输入格式
第一行包含两个整数 :城市的边长和可用塔的数量。
接下来 行,每行包含三个整数 ,表示第 座塔的坐标。
保证每组三元坐标都对应城市中的一座塔,且输入中所有塔互不相同。
数据范围
- ;
- ;
- ;
- 所有输入均为整数。
输出格式
输出一个整数,表示满足要求的三座塔的选择方案数。
样例 1
输入:
2 6
-1 -2 1
2 2 0
-1 1 -2
-1 0 -1
1 1 0
0 1 -1
输出:
1
样例 2
输入:
1 7
0 1 -1
1 1 0
0 -1 1
1 0 1
-1 -1 0
-1 0 -1
0 0 0
输出:
8
附图
下面的网格可辅助理解三角格点:
