| ||||||||||
| 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