平面图绘制（DrawPlanar）

题目背景

在一座正在建设的智慧城市中，规划部门需要在一块矩形区域内布置若干个通信站。部分通信站之间需要铺设笔直的专用线路。为了避免线路相互干扰，任意两条没有公共端点的线路都不能相交，通信站也不能落在与自己无关的线路上。

为了便于施工与测量，所有通信站都必须设置在平面直角坐标系的整点上，每条线路则直接连接对应的两个通信站。由于可用土地十分有限，规划师希望在满足全部连接要求的前提下，使覆盖所有通信站的轴对齐矩形面积尽可能小。

从图论角度看，通信站和线路构成了一个无向平面图。平面图总能在平面上绘制而不产生不合法的边交叉，而本题要求进一步寻找一个面积最小的整点直线绘制方案。

题目描述

给定一个有 $n$ 个顶点的无向平面图，顶点编号为 $1,2,\ldots,n$。

你需要为每个顶点选择一个互不相同的整点坐标 $(x_i,y_i)$，并将每条边画成其两个端点之间的直线段。绘制必须满足：

• 除共同端点外，任意两条边不能相交；
• 任意顶点不能落在一条与它不关联的边的内部；
• 两条不同的边不能有长度为正的重叠部分。

设所有顶点的横坐标范围为

纵坐标范围为

所有顶点均位于一个宽为 $W$、高为 $H$ 的轴对齐矩形中，其面积为 $W\times H$。

请计算满足要求的绘制所能达到的最小矩形面积。

当所有顶点可以放在同一直线上时，$W$ 或 $H$ 可以为 $0$，因此答案可能为 $0$。

输入格式

第一行包含一个整数 $n$，表示顶点数。

接下来 $n$ 行，每行包含一个长度为 $n$ 的字符串。第 $i$ 行的第 $j$ 个字符表示顶点 $i$ 与顶点 $j$ 是否相连：

• T：存在一条无向边；
• F：不存在边。

输出格式

输出一个整数，表示最小矩形面积。

样例 1

1
F

0

样例说明

只有一个顶点时，一个整点就足够，矩形面积为 $0$。

样例 2

3
FTF
TFF
FFF

0

样例说明

三个顶点可以放在同一直线上，且唯一一条边不会经过第三个顶点，因此答案为 $0$。

样例 3

3
FTT
TFT
TTF

1

样例说明

可以选择一个 $1\times 1$ 正方形的三个角放置三个顶点。

样例 4

4
FTTT
TFTT
TTFT
TTTF

4

数据范围

• $1\le n\le 7$；
• 每个字符串长度均为 $n$；
• 字符只可能是 T 或 F；
• 对任意 $i$，第 $i$ 行第 $i$ 个字符为 F；
• 邻接矩阵关于主对角线对称；
• 输入图保证是平面图。