Codeforces Beta Round 62
E
Contact
Codeforces
2900
原题
← D→
翻译中…

Little Petya is preparing for the first contact with aliens. He knows that alien spaceships have shapes of non-degenerate triangles and there will be exactly 4 ships. Landing platform for a ship can be made of 3 special columns located at some points of a Cartesian plane such that these 3 points form a triangle equal to the ship with respect to rotations, translations (parallel shifts along some vector) and reflections (symmetries along the edges). The ships can overlap after the landing.

翻译中…

Each column can be used to land more than one ship, for example, if there are two equal ships, we don't need to build 6 columns to land both ships, 3 will be enough. Petya wants to know what minimum number of columns will be enough to land all ships.

翻译中…

Input

翻译中…

Each of 4 lines will contain 6 integers $*x*_{1}$ $*y*_{1}$ $*x*_{2}$ $*y*_{2}$ $*x*_{3}$ $*y*_{3}$ ($0 ≤ *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2}, *x*_{3}, *y*_{3} ≤ 20$), representing 3 points that describe the shape of each of 4 ships. It is guaranteed that 3 points in each line will represent a non-degenerate triangle.

翻译中…

Output

翻译中…

First line should contain minimum number of columns enough to land all spaceships.

翻译中…

Note

翻译中…

In the first test case columns can be put in these points: $(0, 0), (1, 0), (3, 0), (1, 2)$. Note that the second ship can land using last 3 columns.

翻译中…

In the second test case following points can be chosen: $(0, 0), (0, 1), (1, 0), (0, 2), (2, 0), (0, 5), (5, 0), (0, 17), (17, 0)$. It is impossible to use less than 9 columns.

翻译中…

样例

Input #1
0 0 1 0 1 2
0 0 0 2 2 2
0 0 3 0 1 2
0 0 3 0 2 2
Output #1
4
InputCopy OutputCopy
Input #2
0 0 0 1 1 1
0 0 0 2 2 2
0 0 0 5 5 5
0 0 0 17 17 17
Output #2
9
InputCopy OutputCopy
题目信息
题号
68E
时间限制
3 s
内存限制
256 MB
标签
计算几何

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。