[HOJ 200][COI 2012]SETNJA

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

不知道為甚麼大家都不太敢做這題只有兩個人過的題目(遭踢飛
經過思考可以發現，因為一定要照順序拜訪朋友家，所以繞到其他地方去再繞回來一定沒有比較好，那就乾脆假設主角是筆直的走過去的吧
問題來了，我們並不知道一開始主角在哪，怎麼辦呢？
把他有可能的位置全部考慮進去就好啦(?)
我們可以存一個矩形的左上角和右下角座標代表他用目前最佳步數可能走到的範圍，所以一開始矩形是(-INF,-INF)(INF,INF)(以下稱「出沒範圍」)
接下來開始拜訪朋友家了，可以想成: 朋友家是一個邊長2p的正方形，只要碰到這個正方形就好了
如果目前出沒範圍跟朋友家有交集，那麼從其他地方跑過來一定是吃虧的，所以直接縮小出沒範圍，不用任何花費
如果沒有交集，那麼就算出要碰到朋友家需要的最小花費，假設是dis好了，那麼可以用dis的花費把出沒範圍往周圍擴展dis的距離，再依上述方式縮小出沒範圍就好了

ps.其實這題第一次就AC讓我滿驚訝的，畢竟只有兩個人過感覺就藏一堆陷阱XD

code:

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
int N;
LL ANS,X1,X2,Y1,Y2;
void Update(const LL &x1,const LL &x2,const LL &y1,const LL &y2)
{
    if(max(X1,x1)<=min(X2,x2)&&max(Y1,y1)<=min(Y2,y2))
    {
        X1=max(X1,x1),X2=min(X2,x2),Y1=max(Y1,y1),Y2=min(Y2,y2);
    }
    else
    {
        const LL dis=max(max(X1,x1)-min(X2,x2),max(Y1,y1)-min(Y2,y2));
        X1-=dis,X2+=dis,Y1-=dis,Y2+=dis;
        ANS+=dis;
        Update(x1,x2,y1,y2);
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        ANS=0;
        X1=Y1=-INF,X2=Y2=INF;
        for(int i=0;i<N;i++)
        {
            static LL x,y,p;
            scanf("%lld%lld%lld",&x,&y,&p);
            Update(x-p,x+p,y-p,y+p);
        }
        printf("%lld\n",ANS);
    }
    return 0;
}