#P18801. [POI1998] 多边形

[POI1998] 多边形

[POI1998] 多边形

题目描述

一个凸 nn 边形的顶点沿顺时针方向依次编号为 0,1,…,n−10,1,\ldots,n-1。给定这个多边形的一组三角剖分:它由 n−2n-2 个三角形组成,三角形的顶点均为原多边形的顶点,各三角形的内部互不相交,合起来恰好覆盖原多边形。

从原多边形的顶点中任选三个不同的顶点,构成一个三角形 TT。TT 不必是给定剖分中的三角形。

若两个三角形的内部存在公共点,则称它们相交。仅在边或顶点处接触不算相交。

求 TT 最多能与给定剖分中的多少个三角形相交。

输入格式

第一行一个整数 nn,3≤n≤10003\le n\le1000。

接下来 n−2n-2 行,每行三个整数 a,b,ca,b,c,表示剖分中的一个三角形的三个顶点编号。每行内三个编号的排列顺序不限。

保证输入是一组合法的三角剖分。输入不提供顶点坐标。

输出格式

输出一个整数,表示最多能相交的三角形数量。

样例输入

6
0 2 4
0 1 2
2 3 4
4 5 0

样例输出

4