## 1696: [Usaco2007 Feb]Building A New Barn New cowshed

Time Limit: 5 Sec Memory Limit: 64 MB

Submit: 394 Solved: 181

[Submit][Status][Discuss]

## Description

After years of savings , Farmer JOHN Decided to build a new cowshed . He knows everything N(2 <= N <= 10,000) Where does the cow feed , So he wanted to build the barn in the most convenient place . The position where each cow grazes is an integral point (X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000). No two cows are grazing next to each other . JOHN Decided to build the cowshed at an integer point where no cattle eat grass . If the cowshed is in (X, Y), stay (X_i, Y_i) The distance between your cattle and the barn is |X-X_i|+|Y-Y_i|. JOHN Where can the cowshed be built to minimize the distance between all cattle and the cowshed ？

## Input

The first 1 That's ok ： a number ,N.

The first 2~N+1 That's ok ： The first i+1 That's ok Including i The position of the cow (X_i, Y_i).

## Output

The first 1 That's ok ： Two Numbers , The minimum distance and the number of cowshed positions that can reach this distance sum .

## Sample Input

1 -3

0 1

-2 1

1 -1

Enter an explanation ：

Altogether 4 Head ox , The positions are (1, -3), (0, 1), (-2, 1), and (1, -1).

## Sample Output

Output explanation ：

The minimum distance sum is 10, It can be located in the cowshed (0, -1), (0, 0), (1, 0), (1, 1) Reach at .

## HINT

## Source

Answer key ：

As the topic requires the minimum total distance , So you can think of finding the median .

But proof doesn't ... Find Du Niang by yourself ...

hold x,y Sort them separately .

If the number of cattle is odd , We'll take them separately x,y The middle of the order . And then judge if there are cows . If not, take the current point , If there is, find the minimum value and the number of minimum values in the four points above, below, left and right .( The topic ensures that cows are not adjacent )

If it's an even number , There are two median (x1,y1),(x2,y2). Then the number of answers is (x2-x1+1)*(y2-y1+1)- There are cattle in the middle .

See the procedure ：

#include<bits/stdc++.h>

using namespace std;

#define INF 1e9

int x[],y[],xx[],yy[];

int fx[]={,,,-};

int fy[]={,-,,};

int read()

{

int s=,fh=;char ch=getchar();

while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

return s*fh;

}

int main()

{

freopen("newbarn.in","r",stdin);

freopen("newbarn.out","w",stdout);

int n,i,nn,x1,y1,x2,y2,sum,j,gs,mn;

n=read();

for(i=;i<=n;i++)x[i]=read(),y[i]=read(),xx[i]=x[i],yy[i]=y[i];

sort(xx+,xx+n+);

sort(yy+,yy+n+);

if(n%!=)

{

nn=(n+)/;

x1=xx[nn];

y1=yy[nn];

for(j=;j<=n;j++)if(x[j]==x1&&y[j]==y1)break;

if(j<=n)

{

mn=INF;gs=;

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

{

x2=x1+fx[i];

y2=y1+fy[i];

sum=;

for(j=;j<=n;j++)

{

sum+=(int)fabs(x[j]-x2)+(int)fabs(y[j]-y2);

}

if(sum<mn)

{

mn=sum;gs=;

}

else if(sum==mn)gs++;

}

printf("%d %d",mn,gs);

return ;

}

sum=;

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

{

sum+=(int)fabs(x[i]-x1)+(int)fabs(y[i]-y1);

}

printf("%d 1",sum);

}

else

{

nn=n/;

sum=;

x1=xx[nn];

y1=yy[nn];

sum=;

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

{

sum+=(int)fabs(x[i]-x1)+(int)fabs(y[i]-y1);

}

x2=xx[nn+];

y2=yy[nn+];

gs=(x2-x1+)*(y2-y1+);

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

{

if(x[i]>=x1&&x[i]<=x2&&y[i]>=y1&&y[i]<=y2)

{

gs--;

}

}

printf("%d %d",sum,gs);

}

fclose(stdin);

fclose(stdout);

return ;

}

## Bzoj 1696: [Usaco2007 Feb]Building A New Barn New cowshed Median , More articles on Mathematics

- bzoj 1696: [Usaco2007 Feb]Building A New Barn New cowshed —— Median sort
Description After years of savings , Farmer JOHN Decided to build a new cowshed . He knows everything N(2 <= N <= 10,000) Where does the cow feed , So he wanted to build the barn in the most convenient place . Where each cow grazes ...

- BZOJ 1696 [Usaco2007 Feb]Building A New Barn New cowshed mathematics
The question : link Method : mathematics + simulation analysis : First of all, it's not the first time we've seen this kind of problem , So you know how to take x The median .y The median . The problem is that the discussion is very boring . There is a limitation in the question , The points to be summed cannot be selected . So let's say there's an odd number of points , Find out x Median ...

- 【BZOJ】1696: [Usaco2007 Feb]Building A New Barn New cowshed （ greedy ）
http://www.lydsy.com/JudgeOnline/problem.php?id=1696 The original question requires min(sum{|x-xi|+|y-yi|}), And be sure to look at the topic :“ No two cows are grazing in ...

- BZOJ1696: [Usaco2007 Feb]Building A New Barn New cowshed
n<=10000 A little bit (xi,yi), Find a point different from all the points given , Make the Manhattan distance from this point to all points minimum and find out the number of such points . At first glance, it doesn't look like the median , One odd point, one even piece , And then find out how many of these areas ...

- BZOJ 1626: [Usaco2007 Dec]Building Roads Building roads ( MST )
The square exploded when calculating the distance int The result is WA Once ...... ------------------------------------------------------------------------- ...

- BZOJ 1631: [Usaco2007 Feb]Cow Party( shortest path )
This question is similar to Cai Dashen's this year STOI The second questions as like as two peas in the junior middle school ... Run the shortest path first , And reverse all the edges , Run again , The maximum value of all the points added twice is answer --------------------- ...

- BZOJ 1633: [Usaco2007 Feb]The Cow Lexicon Cow's Dictionary
subject 1633: [Usaco2007 Feb]The Cow Lexicon Cow's Dictionary Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 401 Solv ...

- BZOJ 1632: [Usaco2007 Feb]Lilypad Pond
subject 1632: [Usaco2007 Feb]Lilypad Pond Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 390 Solved: 109[ ...

- BZOJ 1631: [Usaco2007 Feb]Cow Party
subject 1631: [Usaco2007 Feb]Cow Party Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 491 Solved: 362[Sub ...

## Random recommendation

- How to view Huawei EMUI System APK Source code ？
I want to see Huawei recently EMUI Some of the systems inside APK How is it realized . So how to get the system APK Well ? There are two ways : 1. Install pea pods , There is an application management function in the pea pod , You can see all the apps on your phone , Including system application . You can use this work ...

- Codeforces Round #336 (Div. 2)
water A - Saitama Destroys Hotel Simple simulation , Little greedy . In fact, it only requires max (ans, t + f); #include <bits/stdc++.h> using n ...

- iis Support html perform php Output
iis Support html perform php Output 2012-07-25 10:50:23| classification : PHP| report | Font size subscribe stay HTML There's a simple one in PHP Random numbers need to be output , for example : <td backg ...

- Apache One host binds multiple domain names and virtual hosts
Today I studied Apache How to use a host to bind multiple domain names and use 80 port . To put it bluntly, it is to run multiple websites on a single host , And website domain names are used 80 port . The specific method is as follows : 1. Get into Apache conf Catalog , find ht ...

- Block Internet connection
https://www.board4allcz.eu/showthread.php?t=625547

- TSL accessor
Design principle :GE There's a distributed memory infrastructure , Become a memory cloud . The memory cloud consists of a set of memory trunks . Each machine in the cluster carries 256 A memory relay . There are two reasons why we divide the local memory space of a machine into multiple memory relays :1) The parallelism at the relay level can ...

- DBA Record - What database administrators need to master
1.Linux 2.ORACLE/MySQL/SQLSERVER 3.NOSQL 4. The deployment environment . User and permission management . Table space . surface . View . Indexes . The process . trigger . Partition . function . Inquire about . performance tuning . Migration backup . colony . Log points ...

- [UE4] know CanvasPanelSlot,Construct Object From Class Dynamically create UI Control
Canvas Panel Slot yes UserWidget Of Canvas Panel Component specific properties within a component container . Only placed in Canvas Panel Only in the container will there be Canvas Panel Slot attribute can ...

- Python Zero basis Quick start Interesting course ( Dr. mi The turtle drawing turtle) 0. preparation
One . About Python Python It's the fastest growing programming language in the world ! It's easy to get started . Powerful , from Web Back end To Data analysis . Artificial intelligence , You can see... Everywhere Python The figure of . Python There are two main ...

- React Js The components of （Component） And state
React Js Components : Components (Component) In order to better maintain our application , You can update or change components without affecting other components . state: It's the source of the tag data , We make state Relatively simple and single , If we had ...