// #pragma GCC optimize("O3,unroll-loops") #include // #include using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template T &ctmin(T &x){ return x; } template T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min(x, h), t...); } template T &ctmax(T &x){ return x; } template T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max(x, h), t...); } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); static const vector> dr8{{2, 1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}; int n; cin >> n; set> appear; map, int> mask; for(auto i = 0; i < n; ++ i){ int x, y; cin >> x >> y; appear.insert({x, y}); for(auto [dx, dy]: dr8){ mask[{x + dx, y + dy}] |= 1 << i; } } for(auto [x, y]: appear){ mask.erase({x, y}); } const int inf = numeric_limits::max() / 2; vector dp(1 << n, inf); dp[0] = 0; for(auto [pos, m]: mask){ for(auto smask = m; smask; smask = smask - 1 & m){ ctmin(dp[smask], 1); } } for(auto mask = 1; mask < 1 << n; ++ mask){ for(auto smask = mask; smask; smask = smask - 1 & mask){ ctmin(dp[mask], dp[smask] + dp[smask ^ mask]); } } dp.back() == inf ? cout << "-1\n" : cout << dp.back() << "\n"; return 0; } /* */