#include #include #include using namespace std; int gcd(int x, int y) { if(y == 0) return x; return gcd(y, x % y); } int main() { int N; cin >> N; vector X(N), Y(N); for(int i = 0; i < N; ++i) { cin >> X[i] >> Y[i]; } vector > lines; // {a, b, c} --> ax + by + c = 0 for(int i = 0; i < N; ++i) { for(int j = 0; j < i; ++j) { int a = Y[i] - Y[j]; int b = -(X[i] - X[j]); int c = -(a * X[i] + b * Y[i]); int g = gcd(abs(a), gcd(abs(b), abs(c))); if(a < 0 || (a == 0 && b < 0)) { a *= -1, b *= -1, c *= -1; } lines.push_back({a / g, b / g, c / g}); } } sort(lines.begin(), lines.end()); lines.erase(unique(lines.begin(), lines.end()), lines.end()); int ls = lines.size(); vector ok(1 << N, false); ok[0] = true; for(int i = 0; i < N; ++i) { ok[1 << i] = true; } for(int i = 0; i < ls; ++i) { vector online; for(int j = 0; j < N; ++j) { if(lines[i][0] * X[j] + lines[i][1] * Y[j] + lines[i][2] == 0) { online.push_back(j); } } sort(online.begin(), online.end(), [&](int va, int vb) { return lines[i][1] * (X[vb] - X[va]) - lines[i][0] * (Y[vb] - Y[va]) > 0; }); int sz = online.size(); for(int j = 0; j <= sz; ++j) { for(int k = j + 1; k <= sz; ++k) { int bit = 0; for(int l = j; l < k; ++l) { bit |= 1 << online[l]; } ok[bit] = true; } } } /* for(int i = 0; i < ls; ++i) { cout << lines[i][0] << ' ' << lines[i][1] << ' ' << lines[i][2] << endl; } */ for(int i = 0; i < ls; ++i) { for(int j = 0; j < i; ++j) { for(int k = 0; k < j; ++k) { if(lines[i][0] * lines[j][1] == lines[i][1] * lines[j][0]) continue; if(lines[j][0] * lines[k][1] == lines[j][1] * lines[k][0]) continue; if(lines[k][0] * lines[i][1] == lines[k][1] * lines[i][0]) continue; vector pos = { i, j, k }; vector sign(3); bool nonzero = true; for(int w = 0; w < 3; ++w) { int p0 = pos[w], p1 = pos[(w + 1) % 3], p2 = pos[(w + 2) % 3]; long long val0 = lines[p0][2] * (lines[p2][0] * lines[p1][1] - lines[p1][0] * lines[p2][1]); long long val1 = lines[p1][2] * (lines[p0][0] * lines[p2][1] - lines[p2][0] * lines[p0][1]); long long val2 = lines[p2][2] * (lines[p0][0] * lines[p1][1] - lines[p1][0] * lines[p0][1]); long long val = (val0 + val1 - val2) * (lines[p2][0] * lines[p1][1] - lines[p1][0] * lines[p2][1] > 0 ? +1 : -1); if(val == 0) { nonzero = false; break; } sign[w] = (val > 0 ? +1 : -1); } if(!nonzero) continue; int bit = 0; for(int l = 0; l < N; ++l) { int vali = lines[i][0] * X[l] + lines[i][1] * Y[l] + lines[i][2]; int valj = lines[j][0] * X[l] + lines[j][1] * Y[l] + lines[j][2]; int valk = lines[k][0] * X[l] + lines[k][1] * Y[l] + lines[k][2]; if(vali * sign[0] >= 0 && valj * sign[1] >= 0 && valk * sign[2] >= 0) { bit |= 1 << l; } } ok[bit] = true; } } } int res = 0; for(int i = 0; i < (1 << N); ++i) { if(ok[i]) { /* for(int j = 0; j < N; ++j) { cout << ((i >> j) & 1); } cout << endl; */ ++res; } } cout << res << endl; return 0; }