BZOJ 3170: [Tjoi 2013]松鼠聚会切比雪夫距离-白红宇

BZOJ 3170: [Tjoi 2013]松鼠聚会切比雪夫距离

阅读量：5495 次

发布时间：2019-06-16

本文共 1367 字，大约阅读时间需要 4 分钟。

3170: [Tjoi 2013]松鼠聚会

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=3170

Description

有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

Input

第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5

下面N行，每行给出x,y表示其家的坐标。

-10^9<=x,y<=10^9

Output

表示为了聚会走的路程和最小为多少.

Sample Input

6 -4 -1 -1 -2 2 -4 0 2 0 3 5 -2

Sample Output

HINT

题意

题解：

题目给的切比雪夫距离，转化成曼哈顿距离就好了

然后利用前缀和统计一下就行了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 100010#define eps 1e-9int Num;//const int inf=0x7fffffff; //§ß§é§à§é¨f§3const int inf=0x3f3f3f3f;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//**************************************************************************************struct node{ double x,y; int id;}p[maxn];double ans[maxn];bool cmp1(node a,node b){ return a.x