toj 4602 松鼠聚会

题目：

草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点(x-1,y),(x+1,y),(x,y-1),(x,y+1),(x-1,y+1),(x-1,y-1),(x+1,y+1), (x+1,y-1)距离为1。

输入

第一行是一个整数N,表示有多少只松鼠。接下来N行,第i行是两个整数x和y,表示松鼠i的家的坐标。(0≤N≤10⁵,−10⁹≤x,y≤10⁹)

输出

一个整数,表示松鼠为了聚会走的路程和最小是多少。

样例输入1

样例输出1

样例输入2

样例输出2

提示

在第一个样例中,松鼠在第二只松鼠家(-1,-2)聚会;在第二个样例中,松鼠在第一只松鼠家(0,0)聚会

题解：此题中定义的两点间距离，稍加分析就会发现是max(|xi-xj|， |yi-yj|);

此时需要用到一个公式:

　　　　　　　　max（|a|,|b|）=|（a+b）/2|+|（a-b）/2|;

于是，两点间距离成了:

　　　　　　　　|(xi-xj+yi-yj)/2|+|(xi-xj-yi+yj)/2|

　　　　　　= (|(xi+yi) - (xj+yj)| + |(xi-yi)-(xj-yj)|)/2

公式中需要用xi+yi, xi-yi的值，这其实对应于点(xi,yi)在另一个坐标系中的坐标。我们对原来的点坐标做变换，令x'=x+y, y'=x-y,则上面的公式变成了：

　　　　　　　　(|xi'-xj'| + |yi'-yj'|)/2

分析到这儿就好做了，对于给定的点pi, 计算∑(|xi'-xj'| + |yi'-yj'|)/2还是很容易的，先整体做一遍预处理，按x排序计算一遍x坐标的前缀和，再按y排序，计算一次y坐标的前缀和就可以了。

代码如下：

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 #define ll long long

 #define N 101000

 struct point {

     ll x, y;

     ll sx, sy;

     int cx, cy;

 }p[N];

 ll sumx, sumy;

 bool cmpx(point a, point b){

     return a.x < b.x;

 }

 bool cmpy(point a, point b){

     return a.y < b.y;

 }

 int main()

 {

     int n;

     while(~scanf("%d", &n))

     {

         sumx = sumy = ;

         ll x, y;

         for(int i = ; i < n; i++)

         {

             scanf("%lld %lld", &x, &y);

             p[i].x = x+y, p[i].y = x-y;

             sumx += p[i].x, sumy += p[i].y;

         }

         sort(p, p+n, cmpx);

         p[].sx = p[].cx = ;

         for(int i = ; i < n; i++)

         {

             p[i].sx = p[i-].sx + p[i-].x;

             p[i].cx = p[i-].cx + ;

         }

         sort(p, p+n, cmpy);

         p[].sy = p[].cy = ;

         for(int i = ; i < n; i++)

         {

             p[i].sy = p[i-].sy + p[i-].y;

             p[i].cy = p[i-].cy + ;

         }

         ll ans = -;

         for(int i = ; i < n; i++)

         {

             ll tm = p[i].cx*p[i].x - p[i].sx + (sumx-p[i].sx-p[i].x)-((n-p[i].cx-)*p[i].x);

             tm += p[i].cy*p[i].y - p[i].sy + (sumy-p[i].sy-p[i].y)-((n-p[i].cy-)*p[i].y);

             if(ans == - || tm < ans)ans = tm;

         }

         printf("%lld\n", ans/);

     }

     return ;

 }

巴特西

toj 4602 松鼠聚会

输入

输出

样例输入1

样例输出1

样例输入2

样例输出2

提示

最新文章

热门文章