Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
测试数据啊,谁有啊#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define MAX_N 2100 #define MAX_M 2100000 #define oo 0x7fffffff struct node { int t, n; }; struct point { int x, y; }; node e[MAX_M]; int fi[MAX_N], st[MAX_N]; int dfn[MAX_N], low[MAX_N], belong[MAX_N]; bool in[MAX_N]; int p1[MAX_N][2], p2[MAX_N][2]; int d[MAX_N]; point s1, s2; int n, na, nb, tot, ts, top, len; void insert(int a, int b) { e[++tot].t = b, e[tot].n = fi[a], fi[a] = tot; } void dfs(int x) { dfn[x] = low[x] = ++ts, in[st[++top] = x] = true; for (int i = fi[x], t; i != -1; i = e[i].n) { t = e[i].t; if (!dfn[t]) { dfs (t); if (low[t] < low[x]) low[x] = low[t]; } else if (in[t] && dfn[t] < low[x]) low[x] = dfn[t]; } if (dfn[x] == low[x]) while (st[top + 1] != x) { belong[st[top]] = x; in[st[top--]] = false; } } int myabs(int x) { return x < 0 ? -x : x; } int dist(point a, point b) { return myabs (a.x - b.x) + myabs (a.y - b.y); } bool judge(int x) { for (int i = 1; i <= n + n; i++) low[i] = dfn[i] = 0, fi[i] = -1, in[i] = false; tot = 0; for (int i = 1, t1, t2; i <= na; i++) { t1 = p1[i][0], t2 = p1[i][1]; insert (t1, t2 + n), insert (t1 + n, t2); insert (t2, t1 + n), insert (t2 + n, t1); } for (int i = 1, t1, t2; i <= nb; i++) { t1 = p2[i][0], t2 = p2[i][1]; insert (t1, t2), insert (t2, t1); insert (t1 + n, t2 + n); insert (t2 + n, t1 + n); } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) continue; if (d[i] + d[j] > x) insert (i, n + j); if (d[i] + d[n + j] + len > x) insert (i, j); if (d[n + i] + d[j] + len > x) insert (n + i, n + j); if (d[n + i] + d[n + j] > x) insert (n + i, j); } //printf ("%d %d %d\n", lenc, lens, tot); ts = 0; for (int i = 1; i <= n + n; i++) if (!dfn[i]) top = 0, dfs (i); for (int i = 1; i <= n; i++) if (belong[i] == belong[n + i]) return false; return true; } int main(void) { freopen ("2749.in", "r", stdin); freopen ("2749.out", "w", stdout); scanf ("%d%d%d", &n, &na, &nb); scanf ("%d%d%d%d", &s1.x, &s1.y, &s2.x, &s2.y); len = dist (s1, s2); int l = oo, r = -1, mid; for (int i = 1; i <= n; i++) { point t; scanf ("%d%d", &t.x, &t.y); d[i] = dist (t, s1); d[i + n] = dist (t, s2); l = min (l, min (d[i], d[i + n])); r = max (r, max (d[i], d[i + n])); } for (int i = 1; i <= na; i++) scanf ("%d%d", &p1[i][0], &p1[i][1]); for (int i = 1; i <= nb; i++) scanf ("%d%d", &p2[i][0], &p2[i][1]); l = l + l, r = r + r + len; if (!judge (oo)) l = r = -1; while (r - l > 1) { mid = (l + r) / 2; if (judge (mid)) r = mid; else l = mid; } printf ("%d\n", r); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator