2015年4月21日 星期二

2015/04/21 Codeforces 491B. New York Hotel

/*
    非常精妙!!!
    自己想不到 又沒有題解
    只好去看別人的 code =3=

    用到的性質是 對於點對 (i, j)
    他們的曼哈頓距離 一定是 
    max(abs(xi-xj+yi-yj), abs(xi-xj-yi+yj))
*/
// http://codeforces.com/problemset/problem/491/B
#include <iostream>
#include <cstdio>

using namespace std;

#define INF INT_MAX

int C, H;
int mxa = -INF, mna = INF;
int mxb = -INF, mnb = INF;

int main()
{
    scanf("%*d %*d %d", &C);

    for(int Ci = 0; Ci < C; Ci++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        mxa = max(x+y, mxa);
        mna = min(x+y, mna);
        mxb = max(x-y, mxb);
        mnb = min(x-y, mnb);
    }

    scanf("%d", &H);

    int id = -1, Ans = INF;

    for(int Hi = 1; Hi <= H; Hi++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        int p = 0;
        p = max(p, x+y-mna);
        p = max(p, mxa-x-y);
        p = max(p, x-y-mnb);
        p = max(p, mxb-x+y);

        if( p < Ans ) id = Hi, Ans = p;
    }

    printf("%d\n%d\n", Ans, id);
}

沒有留言:

張貼留言