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

4
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

10 4

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

Gold

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

  1. 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 ...

  2. 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 ...

  3. 【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 ...

  4. 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 ...

  5. BZOJ 1626: [Usaco2007 Dec]Building Roads Building roads ( MST )

    The square exploded when calculating the distance int The result is WA Once ...... ------------------------------------------------------------------------- ...

  6. 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 --------------------- ...

  7. 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 ...

  8. BZOJ 1632: [Usaco2007 Feb]Lilypad Pond

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

  9. 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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. Block Internet connection

    https://www.board4allcz.eu/showthread.php?t=625547

  6. 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 ...

  7. 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 ...

  8. [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 ...

  9. 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 ...

  10. 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 ...