#include #define rep(i, l, n) for (int i = (l); i < (n); i++) #define all(x) x.begin(), x.end() #define last(v) v[v.size() - 1] using namespace std; using ll = long long; template using V = vector; struct Fraction { ll num; ll den; static 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; } static ll lcm(ll x, ll y) { ll g = gcd(x, y); return x / g * y; } 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; } static Fraction parsePositive(Fraction x) { if (x.num < 0) { return -x; } return x; } Fraction operator+(void) const { return *this; } Fraction operator-(void) const { return Fraction() - (*this); } 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(); int sgn(Fraction x) { if (zero < x) { return 1; } if (x < zero) { return -1; } return 0; } struct Vector2 { Fraction x; Fraction y; Vector2(void) { x = zero; y = zero; } Vector2(Fraction x, Fraction y) { this->x = x; this->y = y; } static Vector2 normalize(Vector2 v) { assert(v.x != zero or v.y != zero); Fraction norm = v.x * v.x + v.y * v.y; return Vector2(v.x * Fraction::parsePositive(v.x) / norm, v.y * Fraction::parsePositive(v.y) / norm); } Vector2 operator+(const Vector2 other) const { return Vector2(other.x + this->x, other.y - this->y); } Vector2 operator-(const Vector2 other) const { return Vector2(other.x - this->x, other.y - this->y); } Fraction operator*(const Vector2 other) const { return this->x * other.y - this->y * other.x; } 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); } bool operator!=(const Vector2 other) const { return tie(this->x, this->y) != tie(other.x, other.y); } }; const Vector2 zeroVector = Vector2(); /* * 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; } V > vectors(N, V(N)); rep(i, 0, N - 1) { rep(j, i + 1, N) { vectors[i][j] = Vector2::normalize(P[j] - P[i]); vectors[j][i] = Vector2::normalize(P[i] - P[j]); } } 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 = { vectors[num[0]][num[1]] }; rep(i, 1, N - 1) { Vector2 v = vectors[num[i]][num[i + 1]]; if (last(vec) == v) { continue; } if (last(vec) * v == zero) { flag = true; break; } vec.push_back(v); } if (flag) { continue; } int M = vec.size(); if (M <= 2) { ans = min(ans, M); continue; } V > dp(M - 1, { -1,-1 }); dp[0].first = 0; rep(i, 1, M - 1) { Vector2 v1 = vec[i - 1], v2 = vec[i], v3 = vec[i + 1]; int s1 = sgn(v1 * v2), s2 = sgn(v2 * v3), s3 = sgn(v1 * v3); if (s1 == s2 and s2 == s3) { dp[i].second = dp[i - 1].first + 1; } dp[i].first = max(dp[i - 1].first, dp[i - 1].second); } ans = min(ans, M - max(dp[M - 2].first, dp[M - 2].second)); } while (next_permutation(all(num))); cout << ans << endl; return 0; }