"""Simulated annealing for Heilbronn's problem: maximise the smallest triangle area."""
import itertools
import math
import random
import sys


def min_area(p):
    return min(abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2 for a, b, c in itertools.combinations(p, 3))


def anneal(n, steps=20000, seed=0):
    rng = random.Random(seed)
    p = [(rng.random(), rng.random()) for _ in range(n)]
    cur = best = min_area(p)
    best_p = p[:]
    for k in range(steps):
        t = 0.01 * (1 - k / steps) + 1e-6
        i = rng.randrange(n)
        old = p[i]
        p[i] = tuple(min(1, max(0, c + rng.gauss(0, t))) for c in old)
        new = min_area(p)
        if new >= cur or rng.random() < math.exp((new - cur) / t):
            cur = new
            if new > best:
                best, best_p = new, p[:]
        else:
            p[i] = old
    return best, best_p


if __name__ == "__main__":
    n = int(sys.argv[1])
    restarts = int(sys.argv[2]) if len(sys.argv) > 2 else 40
    steps = int(sys.argv[3]) if len(sys.argv) > 3 else 20000
    best = max((anneal(n, steps, seed=s) for s in range(restarts)), key=lambda r: r[0])
    print(f"# n={n} min area {best[0]:.6f}")
    for x, y in best[1]:
        print(f"{x:.6f} {y:.6f}")