/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include #include #include using namespace std; FILE *in; FILE *out; // Dinitz Algorithm const int MAX_NODES = 32768; const int MAX_EDGES = 2097152; const int INF = 1000000001; struct Edge { int next, to, cap; Edge(int next_ = 0, int to_ = 0, int cap_ = 0) : next(next_), to(to_), cap(cap_) {} }; int source, sink; Edge edges[MAX_EDGES]; int numEdges; int vis[MAX_NODES], dist[MAX_NODES], first[MAX_NODES]; int recurse(int node, int flow) { if (node == sink) return flow; for (int idx = first[node]; idx != -1; idx = edges[idx].next) { if (!vis[edges[idx].to] && edges[idx].cap > 0 && dist[node] == dist[edges[idx].to] + 1) { int ret = recurse(edges[idx].to, min(flow, edges[idx].cap)); if (ret) {edges[idx].cap -= ret; edges[idx ^ 1].cap += ret; return ret;} } } vis[node] = 1; return 0; } int dinitz(int source_, int sink_) { source = source_; sink = sink_; int flow = 0; while (true) { // BFS int cur = 0; queue q; for (int i=0; i 0 && dist[edges[idx].to] == MAX_NODES) { dist[edges[idx].to] = dist[cur] + 1; q.push(edges[idx].to); if (edges[idx].to == source) {cur = source; break;} } } if (cur == source) break; } if (cur != source) break; // DFS int flag = 0; memset(vis, 0, sizeof(vis)); while (true) { int add = recurse(source, INF); if (add == 0) break; flow += add; flag = 1; } if (!flag) break; } return flow; } inline void addEdge(int from, int to, int cap) { edges[numEdges].to = to; edges[numEdges].cap = cap; edges[numEdges].next = first[from]; first[from] = numEdges++; edges[numEdges].to = from; edges[numEdges].cap = 0; edges[numEdges].next = first[to]; first[to] = numEdges++; } // End of Dinitz Algorithm const int MAX = 10004; const double EPS = 0.000001; const double PI = 3.141592653589793; const double DEG2RAD = PI / 180.0; int d; int a[MAX], n, m, k; int b[MAX], p, q, r; bool isTri(int idx, int t1, int t2, int t3) { return idx < t1; } bool isRec(int idx, int t1, int t2, int t3) { return idx >= t1 && idx < t1 + t2; } bool isCir(int idx, int t1, int t2, int t3) { return idx >= t1 + t2; } bool matchTriTri(int s1, int s2) { if (s1 < s2 - d) return false; return s1 <= s2; } bool matchTriRec(int s1, int s2) { if (s1 < s2 - d) return false; return (double)s1 * cos(DEG2RAD * 15.0) < s2 + EPS; } bool matchTriCir(int s1, int s2) { if (s1 < s2 - d) return false; return (double)s1 * 2.0 * sqrt(3.0) < 3.0 * s2 + EPS; } bool matchRecTri(int s1, int s2) { if (s1 < s2 - d) return false; return 2LL * s1 <= s2; } bool matchRecRec(int s1, int s2) { if (s1 < s2 - d) return false; return s1 <= s2; } bool matchRecCir(int s1, int s2) { if (s1 < s2 - d) return false; return 2LL * s1 * s1 <= (long long)s2 * s2; } bool matchCirTri(int s1, int s2) { if (s1 < s2 - d) return false; return 3.0 * s1 < (double)s2 * sqrt(3.0) + EPS; } bool matchCirRec(int s1, int s2) { if (s1 < s2 - d) return false; return s1 <= s2; } bool matchCirCir(int s1, int s2) { if (s1 < s2 - d) return false; return s1 <= s2; } void solve() { numEdges = 0; memset(first, -1, sizeof(first)); for (int i = 0; i < n + m + k; i++) { for (int c = 0; c < p + q + r; c++) { bool canMatch = false; if (isTri(i, n, m, k)) { if (isTri(c, p, q, r) && matchTriTri(a[i], b[c])) canMatch = true; if (isRec(c, p, q, r) && matchTriRec(a[i], b[c])) canMatch = true; if (isCir(c, p, q, r) && matchTriCir(a[i], b[c])) canMatch = true; } else if (isRec(i, n, m, k)) { if (isTri(c, p, q, r) && matchRecTri(a[i], b[c])) canMatch = true; if (isRec(c, p, q, r) && matchRecRec(a[i], b[c])) canMatch = true; if (isCir(c, p, q, r) && matchRecCir(a[i], b[c])) canMatch = true; } else { if (isTri(c, p, q, r) && matchCirTri(a[i], b[c])) canMatch = true; if (isRec(c, p, q, r) && matchCirRec(a[i], b[c])) canMatch = true; if (isCir(c, p, q, r) && matchCirCir(a[i], b[c])) canMatch = true; } if (canMatch) addEdge(i, n + m + k + c, 1); } } int all = n + m + k + p + q + r; int source = all, sink = all + 1; for (int i = 0; i < n + m + k; i++) addEdge(source, i, 1); for (int i = 0; i < p + q + r; i++) addEdge(n + m + k + i, sink, 1); int flow = dinitz(source, sink); fprintf(out, "%d\n", flow); for (int cur = 0; cur < n + m + k; cur++) { for (int idx = first[cur]; idx != -1; idx = edges[idx].next) { if (edges[idx].cap == 0 && edges[idx].to >= n + m + k && edges[idx].to < source) { fprintf(out, "%d %d\n", cur + 1, edges[idx].to - n - m - k + 1); /* int other = edges[idx].to - n - m - k; fprintf(out, "%s with s = %d in %s with s = %d\n", isTri(cur, n, m, k) ? "Triangle" : (isRec(cur, n, m, k) ? "Square" : "Circle"), a[cur], isTri(other, p, q, r) ? "Triangle" : (isRec(other, p, q, r) ? "Square" : "Circle"), b[other]); */ } } } } int main(void) { in = stdin; out = stdout; in = fopen("wizard.in", "rt"); out = fopen("wizard.out", "wt"); fscanf(in, "%d %d %d", &n, &m, &k); for (int i = 0; i < n + m + k; i++) fscanf(in, "%d", &a[i]); fscanf(in, "%d %d %d", &p, &q, &r); for (int i = 0; i < p + q + r; i++) fscanf(in, "%d", &b[i]); fscanf(in, "%d", &d); solve(); return 0; }