#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; } vector > online(ls), orth(ls); for(int i = 0; i < ls; ++i) { for(int j = 0; j < N; ++j) { if(lines[i][0] * X[j] + lines[i][1] * Y[j] + lines[i][2] == 0) { online[i].push_back(j); orth[i].push_back(lines[i][1] * X[j] - lines[i][0] * Y[j]); } } sort(online[i].begin(), online[i].end(), [&](int va, int vb) { return lines[i][1] * (X[vb] - X[va]) - lines[i][0] * (Y[vb] - Y[va]) > 0; }); sort(orth[i].begin(), orth[i].end()); } for(int i = 0; i < ls; ++i) { for(int j = 0; j < i; ++j) { if(lines[i][0] * lines[j][1] != lines[i][1] * lines[j][0]) continue; bool swapflag = false; if(lines[i][2] > lines[j][2]) { swap(i, j); swapflag = true; } for(int k = 0; k < ls; ++k) { 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 sign = { -1, +1, 0 }; for(int w1 : orth[i]) { for(int w2 : orth[j]) { for(int w3 : orth[k]) { for(int b = 0; b < 16; ++b) { sign[2] = ((b & 8) ? +1 : -1); 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 == 0) vali += (lines[i][1] * X[l] - lines[i][0] * Y[l] >= w1 ? +1 : -1) * ((b & 1) ? +1 : -1); if(valj == 0) valj += (lines[j][1] * X[l] - lines[j][0] * Y[l] >= w2 ? +1 : -1) * ((b & 2) ? +1 : -1); if(valk == 0) valk += (lines[k][1] * X[l] - lines[k][0] * Y[l] >= w3 ? +1 : -1) * ((b & 4) ? +1 : -1); if(vali * sign[0] >= 0 && valj * sign[1] >= 0 && valk * sign[2] >= 0) { bit |= 1 << l; } } // cout << i << ' ' << j << ' ' << bit << endl; ok[bit] = true; } } } } } if(swapflag) { swap(i, j); } } } for(int i = 0; i < ls; ++i) { int sz = online[i].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[i][l]; } ok[bit] = true; } } } 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; for(int w1 : orth[i]) { for(int w2 : orth[j]) { for(int w3 : orth[k]) { for(int b = 0; b < 8; ++b) { 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 == 0) vali += (lines[i][1] * X[l] - lines[i][0] * Y[l] >= w1 ? +1 : -1) * ((b & 1) ? +1 : -1); if(valj == 0) valj += (lines[j][1] * X[l] - lines[j][0] * Y[l] >= w2 ? +1 : -1) * ((b & 2) ? +1 : -1); if(valk == 0) valk += (lines[k][1] * X[l] - lines[k][0] * Y[l] >= w3 ? +1 : -1) * ((b & 4) ? +1 : -1); 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]) { ++res; } } cout << res << endl; return 0; }