#include #define sgn(x) ((x) < 0 ? -1 : ((x) == 0 ? 0 : 1)) using namespace std; template using V = vector; template struct Vector2 { T x; T y; Vector2(void) { } Vector2(T x, T y) { this->x = x; this->y = y; } static Vector2 normalize(Vector2 v) { T norm = v.x * v.x + v.y * v.y; return Vector2(v.x * T::parsePositive(v.x) / norm, v.y * T::parsePositive(v.y) / norm); } static bool same_inclination(Vector2& v1, Vector2& v2) { return (v1 * v2 == 0 and (v1.x * v2.x > 0 or v1.y * v2.y > 0)); } 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); } T 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); } }; int main(void) { int N; cin >> N; V > P(N); for (auto& p : P) { cin >> p.x >> p.y; } if (N == 1) { cout << 1 << endl; return 0; } V > > vec_lis(N, V >(N)); V > > dp(1 << N, V >(N, V(N, N))); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) { continue; } vec_lis[i][j] = P[j] - P[i]; dp[(1 << i) | (1 << j)][i][j] = 1; } } int goal = (1 << N) - 1; for (int b_now = 3; b_now < goal; ++b_now) { for (int v_prev = 0; v_prev < N; ++v_prev) { for (int v_now = 0; v_now < N; ++v_now) { if (v_prev == v_now or dp[b_now][v_prev][v_now] == N or ((b_now >> v_prev) & 1) == 0 or ((b_now >> v_now) & 1) == 0) { continue; } int c_now = dp[b_now][v_prev][v_now], c_next = 0; Vector2& v1 = vec_lis[v_prev][v_now]; for (int v_next1 = 0; v_next1 < N; ++v_next1) { for (int v_next2 = 0; v_next2 < N; ++v_next2) { if (v_next1 == v_next2 or (((b_now >> v_next1) & 1) and v_now != v_next1) or ((b_now >> v_next2) & 1)) { continue; } int b_next = b_now | (1 << v_next1) | (1 << v_next2); Vector2& v2 = vec_lis[v_now][v_next1], v3 = vec_lis[v_next1][v_next2]; if (v_now == v_next1) { c_next = c_now + 1 - Vector2::same_inclination(v1, v3); } else { int d = Vector2::same_inclination(v1, v2) + Vector2::same_inclination(v2, v3); if (d == 0) { d = (sgn(v1 * v2) == sgn(v2 * v3) == sgn(v1 * v3)); } c_next = c_now + 2 - d; } if (dp[b_next][v_next1][v_next2] <= c_next) { continue; } dp[b_next][v_next1][v_next2] = c_next; } } } } } int ans = N; for (auto v: dp[goal]) { for (auto k : v) { if (ans <= k) { continue; } ans = k; } } cout << ans << endl; return 0; }