Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

测试数据啊,谁有啊

Posted by lz1 at 2012-03-03 21:46:02 on Problem 2749
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator