(TIOJ) 1293 . I.送貨倉庫 [切比雪夫距離 --> 曼哈頓距離]

http://tioj.infor.org/problems/1293

坐標系的轉換(?)

在解這題之前，可以先去看看這裡。

有了上面那個之後，應該就不難了XDD。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int N = 1e5 + 6;

LL x[N],y[N],t[N];

#define F first
#define S second
#define SZ(x) ((int)(x).size())

LL abss(LL x)
{
    if (x>0) return x;
    else return -x;
}

vector<pii> vx,vy;

vector<LL> solve(vector<pii> v)
{
    vector<LL> ret;
    LL sum=0;
    for (pii p:v)
    {
        sum += p.S;
    }
    LL pre=0;
    for (int i=0;SZ(v)>i;i++)
    {
        pre += v[i].S;
        if ((sum%2==1))
        {
            if (2*pre > sum)
            {
                ret.push_back(v[i].F);
                break;
            }
        }
        else
        {
            if (2*pre == sum)
            {
                ret.push_back(v[i].F);
                ret.push_back(v[i+1].F);
                ret.push_back(v[i].F+1);
                ret.push_back(v[i+1].F-1);
                break;
            }
            else if (2*pre > sum)
            {

                ret.push_back(v[i].F);
                break;
            }
        }
    }
    return ret;
}

#define __int128 long double

__int128 cal(LL x, LL y, __int128 ans)
{
    __int128 ret=0;
    for (pii p:vx)
    {
        ret += p.S * abss(x-p.F);
        if (ret > ans) return ret;
    }
    for (pii p:vy)
    {
        ret += p.S * abss(y-p.F);
        if (ret > ans) return ret;
    }
    return ret;
}

LL to_x(LL x,LL y)
{
    return (x+y)/2;
}

LL to_y(LL x,LL y)
{
    return (x-y)/2;
}

void update(__int128 &ans,LL &ansx, LL &ansy, LL x0,LL y0)
{
    if ((x0 + y0)&1) return;
    __int128 ret = cal(x0,y0,ans);
    if (ret < ans || ret == ans && make_pair(to_x(x0,y0),to_y(x0,y0)) < make_pair(ansx,ansy))
    {
        ans = ret;
        ansx = to_x(x0,y0);
        ansy = to_y(x0,y0);
    }
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        vx.clear();
        vy.clear();
        for (int i=1;n>=i;i++)
        {
            scanf("%lld %lld %lld",&x[i],&y[i],&t[i]);
            vx.push_back(make_pair(x[i]+y[i],t[i]));
            vy.push_back(make_pair(x[i]-y[i],t[i]));
        }
        sort(vx.begin(),vx.end());
        sort(vy.begin(),vy.end());
        __int128 ans = (1LL<<62) + ( (1LL<<62)-1 );
        ans = ans * ans;
        LL ansx = (1LL<<62);
        LL ansy = (1LL<<62);
        vector<LL> retx=solve(vx),rety=solve(vy);
        int dx[9] = {-1,0,1,-1,0,1,-1,0,1},dy[9] = {-1,-1,-1,0,0,0,1,1,1};
        for (LL x0:retx)
        {
            for (LL y0:rety)
            {
                for (int i=0;9>i;i++)
                {
                    LL x=x0+dx[i],y=y0+dy[i];
                    update(ans,ansx,ansy,x,y);
                }
            }
        }
        printf("%lld %lld\n",ansx,ansy);
    }
}