#include #define rep(i, l, n) for (int i = (l); i < (n); i++) #define inf 1000000000 using namespace std; using ll = long long; template using V = vector; inline ll gcd(ll x, ll y) { x = abs(x); y = abs(y); while (y != 0) { ll r = x % y; x = y; y = r; } return x; } inline ll lcm(ll x, ll y) { ll g = gcd(x, y); return x / g * y; } struct Fraction { ll num; ll den; Fraction(void) { num = 0ll; den = 1ll; } Fraction(ll num, ll den) { assert(den != 0); ll g = gcd(num, den); num /= g; den /= g; if (den < 0) { num = -num; den = -den; } this->num = num; this->den = den; } Fraction operator+(const Fraction other) const { ll l = lcm(this->den, other.den); ll a = l / this->den; ll b = l / other.den; ll nnum = this->num * a + other.num * b; ll nden = l; return Fraction(nnum, nden); } Fraction operator-(const Fraction other) const { Fraction f = Fraction(-other.num, other.den); return (*this) + f; } Fraction operator*(const Fraction other) const { ll nnum = this->num * other.num; ll nden = this->den * other.den; return Fraction(nnum, nden); } Fraction operator/(const Fraction other) const { Fraction f = Fraction(other.den, other.num); return (*this) * f; } bool operator<(const Fraction other) const { ll l = lcm(this->den, other.den); ll a = l / this->den; ll b = l / other.den; return (this->num * a < other.num* b); } bool operator==(const Fraction other) const { ll l = lcm(this->den, other.den); ll a = l / this->den; ll b = l / other.den; return (this->num * a == other.num * b); } bool operator!=(const Fraction other) const { return (((*this) == other) == false); } }; const Fraction zero = Fraction(); inline Fraction abs_frac(Fraction x) { return ((x < zero) ? zero - x : x); } struct Vector2 { Fraction x; Fraction y; Vector2(void) { x = zero; y = zero; } Vector2(Fraction x, Fraction y) { this->x = x; this->y = y; } Vector2 operator-(const Vector2 other) const { return Vector2(other.x - this->x, other.y - this->y); } bool operator<(const Vector2 other) const { return tie(this->x, this->y) < tie(other.x, other.y); } bool operator!=(const Vector2 other) const { return tie(this->x, this->y) != tie(other.x, other.y); } }; struct Line { Fraction a; Fraction b; Fraction c; Line(void) { a = zero; b = zero; c = zero; } Line(Fraction a, Fraction b, Fraction c) { this->a = a; this->b = b; this->c = c; } bool operator<(const Line other) const { return tie(this->a, this->b, this->c) < tie(other.a, other.b, other.c); } }; Line calcLine(Vector2 one, Vector2 other) { Fraction x1 = one.x, y1 = one.y; Fraction x2 = other.x, y2 = other.y; if (x1 == x2) { return Line(Fraction(1ll, 1ll), Fraction(0ll, 1ll), x1); } Fraction a = (y1 - y2) / (x1 - x2); Fraction c = y1 - a * x1; return Line(zero - a, Fraction(1ll, 1ll), c); } Vector2* calcIntersection(Line one, Line other) { Fraction p = one.a * other.b - other.a * one.b; if (p == zero) { return nullptr; } Fraction q = other.b * one.c - one.b * other.c; Fraction x = q / p; Fraction y = (one.b == zero) ? ((other.c - other.a * x) / other.b) : ((one.c - one.a * x) / one.b); return new Vector2(x, y); } Vector2 normalize_vector(Vector2 v) { assert(v.x != zero or v.y != zero); Fraction norm = v.x * v.x + v.y * v.y; return Vector2(v.x * abs_frac(v.x) / norm, v.y * abs_frac(v.y) / norm); } /* * Main Code */ int main(void) { // 入力 int N; cin >> N; V P(N); rep(i, 0, N) { ll x, y; cin >> x >> y; P[i] = { Fraction(x,1ll),Fraction(y,1ll) }; } // 点が1個のときは必ず答え1 if (N == 1) { cout << 1 << endl; return 0; } // 各点に番号付け map ph = {}; int pt_id = 0; for (Vector2& p : P) { ph[p] = pt_id; pt_id++; } // 有り得る直線を調べて番号付け int ln_id = 0; map lh = {}; V vec = {}; rep(i, 0, N - 1) { rep(j, i + 1, N) { Vector2 p1 = P[i], p2 = P[j]; Line l = calcLine(p1, p2); if (lh.find(l) != lh.end()) { continue; } lh[l] = ln_id; ln_id++; vec.push_back(l); } } // 有り得る交点を調べて番号付け rep(i, 0, ln_id - 1) { rep(j, i + 1, ln_id) { Line l1 = vec[i], l2 = vec[j]; Vector2* p = calcIntersection(l1, l2); if (p == nullptr or ph.find(*p) != ph.end()) { continue; } P.push_back(*p); ph[*p] = pt_id; pt_id++; } } //任意の2点について、2点から構成されるベクトルを調べて正規化 V > vectors(pt_id, V(pt_id)); rep(i, 0, pt_id - 1) { rep(j, i + 1, pt_id) { vectors[i][j] = normalize_vector(P[j] - P[i]); vectors[j][i] = normalize_vector(P[i] - P[j]); } } // グラフ探索 V > > dp(1 << N, V >(pt_id, V(pt_id, inf))); deque > que = {}; rep(i, 0, N) { que.push_back({ 0, 1 << i, i, i }); dp[1 << i][i][i] = 0; } int goal = (1 << N) - 1; int ans = inf; int cnt = 0; while (que.empty() == false) { V vec = que.front(); que.pop_front(); int c = vec[0], b = vec[1], lv = vec[2], v = vec[3]; if (c > dp[b][lv][v]) { continue; } if (b == goal) { ans = c; break; } rep(nv, 0, pt_id) { if (v == nv or lv == nv or min(v, nv) >= N) { continue; } int nb = (nv < N) ? (b | (1 << nv)) : b; int nc = c; if (lv == v or vectors[lv][v] != vectors[v][nv]) { nc++; } if (nc >= dp[nb][v][nv]) { continue; } dp[nb][v][nv] = nc; if (nc == c) { que.push_front({ nc, nb, v, nv }); } else { que.push_back({ nc, nb, v, nv }); } } } cout << ans << endl; return 0; }