1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <string> #include <set> using namespace std;
typedef long long LL; const int maxn = 15; int ans, p[maxn]; int r[maxn], st[maxn]; struct Node { int x, y; bool operator < (const Node& rhs) const { return y < rhs.y || (y == rhs.y && x < rhs.x); } } a[maxn];
bool dfs2(int u, int fa, int n) { if (r[p[u]] == -1) { return false; } st[u] = true; if (st[r[p[u]]] || dfs2(r[p[u]], u, n)) { return true; } st[u] = false; return false; }
bool check(int n) { memset(st, 0, sizeof st); for (int i = 0; i < n; ++i) { if (r[i] == p[i]) { return true; } if (dfs2(i, -2, n)) { return true; } } return false; }
void dfs(int d, int n) { if (d == n) { if (check(n)) { ++ans; } return; } if (p[d] == -1) { for (int i = d + 1; i < n; ++i) { if (p[i] == -1) { p[i] = d; p[d] = i; dfs(d + 1, n); p[d] = p[i] = -1; } } } else { dfs(d + 1, n); } }
int main() { freopen("wormhole.in", "r", stdin); freopen("wormhole.out", "w", stdout); int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d%d", &a[i].x, &a[i].y); p[i] = r[i] = -1; } sort(a, a + n); for (int i = 1; i < n; ++i) { if (a[i - 1].y == a[i].y) { r[i - 1] = i; } } dfs(0, n); printf("%d\n", ans); return 0; }
|