#P18765. Captain Thrawn

Captain Thrawn

Captain Thrawn

题目描述

奇斯统治领的索龙上校(Captain Thrawn)被困在帕塔图斯人的母星。他必须把一条重要信息传给阿拉兰尼上将,又等不及友方星舰前来接应,因此需要架设一套由三个部件组成的通信三联装置。三个部件之间的欧几里得距离必须两两相等且非零,也就是放在一个等边三角形的三个顶点上。

由于双方关系紧张,帕塔图斯政府不允许他随意放置装置。帕塔图斯首都是一个边长为 ll 的正六边形,城中道路布局如下。

  • 有 2l+12l+1 条等间距、相互平行、由西向东的街道(street),从南到北编号为 −l,−l+1,…,l-l,-l+1,\ldots,l。街道 −l-l 与正六边形最南边重合,街道 ll 与最北边重合,街道 00 经过中心。
  • 有 2l+12l+1 条等间距、相互平行、由西北向东南的大道(avenue),从西南到东北编号为 −l,−l+1,…,l-l,-l+1,\ldots,l。大道 −l-l 与正六边形的西南边重合,大道 ll 与东北边重合,大道 00 经过中心。
  • 还有 2l+12l+1 条等间距、相互平行、由西南向东北的林荫道(boulevard),从东南到西北编号为 −l,−l+1,…,l-l,-l+1,\ldots,l。林荫道 −l-l 与正六边形的东南边重合,林荫道 ll 与西北边重合,林荫道 00 经过中心。

下图是 l=2l=2 时的城市布局(保留原图的英文道路标注):

l=2 时的街道、大道与林荫道

每个街道、大道与林荫道的交点都有一座塔。如果经过该塔的街道编号为 xx、大道编号为 yy、林荫道编号为 zz,则称塔的坐标为 (x,y,z)(x,y,z)。每座塔都属于某位帕塔图斯官员。

有些官员曾得到索龙的帮助,愿意让他把装置部件放在自己的塔上。他们一共拥有 nn 座可用的塔。索龙需要从中选出三座,使它们两两距离相等,从而架设通信装置。

请计算可以选择这三座塔的方案数。选取的三座塔必须互不相同,三角形边长必须非零;同一组塔不因选取顺序不同而重复计数。

输入格式

第一行包含两个整数 l,nl,n:城市的边长和可用塔的数量。

接下来 nn 行,每行包含三个整数 xi,yi,zix_i,y_i,z_i,表示第 ii 座塔的坐标。

保证每组三元坐标都对应城市中的一座塔,且输入中所有塔互不相同。

数据范围

  • 1≤l≤5001\le l\le500;
  • 1≤n≤3l(l+1)+11\le n\le3l(l+1)+1;
  • −l≤xi,yi,zi≤l-l\le x_i,y_i,z_i\le l;
  • 所有输入均为整数。

输出格式

输出一个整数,表示满足要求的三座塔的选择方案数。

样例 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

附图

下面的网格可辅助理解三角格点:

三角形网格