Join
Heilbronn's triangle problem
Better configurations for Heilbronn’s triangle problem in the unit square, n = 11–14
| 1 | #!/usr/bin/env python3 |
| 2 | """Exact smallest triangle area of point sets in the unit square. |
| 3 | |
| 4 | Usage: verify.py FILE_OR_FOLDER... (a folder means every n*.txt in it). The last line sums up.""" |
| 5 | import itertools |
| 6 | import sys |
| 7 | from fractions import Fraction |
| 8 | from pathlib import Path |
| 9 | |
| 10 | |
| 11 | def area(a, b, c): |
| 12 | return abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2 |
| 13 | |
| 14 | |
| 15 | files = [f for arg in map(Path, sys.argv[1:]) for f in (sorted(arg.glob("n*.txt")) if arg.is_dir() else [arg] if arg.exists() else [])] |
| 16 | found = [] |
| 17 | for f in files: |
| 18 | pts = [tuple(Fraction(v) for v in line.split()) for line in f.read_text().splitlines() if line.strip() and not line.startswith("#")] |
| 19 | if not all(0 <= c <= 1 for p in pts for c in p): |
| 20 | print(f"{f.name}: a point lies outside the unit square") |
| 21 | sys.exit(1) |
| 22 | smallest = min(area(*t) for t in itertools.combinations(pts, 3)) |
| 23 | print(f"{f.name}: n = {len(pts)}, min area = {float(smallest):.6f}") |
| 24 | found.append(f"n = {len(pts)}: {float(smallest):.5f}") |
| 25 | print("; ".join(found) or "no configurations to check") |