#include #define rep(i, l, n) for (int i = (l); i < (n); i++) #define abs(x) (((x) < 0) ? -(x) : (x)) #define all(x) x.begin(), x.end() #define last(v) v[v.size() - 1] #define inf 1000000000 #define INF Fraction(1000000000000000000ll, 1ll) using namespace std; using ll = long long; template using V = vector; inline bool isContinuousBit(int bit) { bool flag = false; while (bit) { if ((bit & 3) == 3) { flag = true; break; } bit >>= 1; } return flag; } 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); } }; inline int sgn(Fraction x) { if (Fraction() < x) { return 1; } if (x < Fraction()) { return -1; } return 0; } struct Vector2 { Fraction x; Fraction y; Vector2(void) { x = Fraction(); y = Fraction(); } Vector2(Fraction x, Fraction y) { this->x = x; this->y = y; } Vector2 operator+(const Vector2 other) const { return Vector2(this->x + other.x, this->y + other.y); } Vector2 operator-(const Vector2 other) const { return Vector2(this->x - other.x, this->y - other.y); } bool operator<(const Vector2 other) const { return tie(this->x, this->y) < tie(other.x, other.y); } bool isNull(void) { return (this->x == INF and this->y == INF); } void show(void) { cout << '(' << this->x.num << " / " << this->x.den << ", " << this->y.num << " / " << this->y.den << ')' << endl; } }; inline bool isSmaeInclination(Vector2 one, Vector2 other) { if (one.x == Fraction()) { return (other.x == Fraction() and Fraction() < one.y / other.y); } Fraction a = other.x / one.x; return (a * one.y == other.y and Fraction() < a); } inline Fraction calcOuterProduct(Vector2 one, Vector2 other) { return one.x * other.y - one.y * other.x; } /* * 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) }; } if (N == 1) { cout << 1 << endl; return 0; } int ans = N; V num(N); rep(i, 0, N) { num[i] = i; } do { bool flag = false; V p(N); rep(i, 0, N) { p[i] = P[num[i]]; } V vec = { p[1] - p[0] }; rep(i, 1, N - 1) { Vector2 v = p[i + 1] - p[i]; if (isSmaeInclination(last(vec), v)) { continue; } if (calcOuterProduct(last(vec), v) == Fraction()) { flag = true; break; } vec.push_back(v); } if (flag) { continue; } int M = vec.size(); if (M <= 2) { ans = min(ans, M); continue; } rep(i, 0, 1 << (M - 2)) { if (isContinuousBit(i)) { continue; } int bit = i << 1; int cnt = M; rep(j, 1, M - 1) { if (((bit >> j) & 1) == 0) { continue; } Vector2 v1 = vec[j - 1], v2 = vec[j], v3 = vec[j + 1]; int s1 = sgn(calcOuterProduct(v1, v2)); int s2 = sgn(calcOuterProduct(v2, v3)); int s3 = sgn(calcOuterProduct(v1, v3)); if (s1 == s2 and s2 == s3) { cnt--; } } ans = min(ans, cnt); } } while (next_permutation(all(num))); cout << ans << endl; return 0; }