1395. 安装服务器

时间限制 1000 ms   内存限制 128 MB

政府计划建立一个大型的服务器中心,为各个城市提供网络服务。每个城市对网络的需求量是不一样的,而需求量越大,对线路的要求也就越高,线路的成本也就越高。因此需要选择合适的地点修建。每个城市用一个二维整数坐标表示,两个点之间的距离定义为水平距离+垂直距离,即a,b两点间距离为D(a,b)=|Xa-Xb|+|Ya-Yb|。对于每个城市,线路的费用为:费用=距离×人口×城市的网络需求程度。总的费用为各个城市的费用的总和。请你找出最适合安装服务器(既总费用最小)的整数坐标(不一定要在城市上)。

输入数据

输入第一行有一个正整数N(N&nbsp ≤&nbsp 100000),表示城市的数量。后面的n行每行描述一个城市,每行有四个整数x,y,p,k分别表示城市的坐标,人口数,以及网络需求程度。(0&nbsp < &nbsp x,&nbsp y&nbsp < &nbsp 2^31;p≤600,&nbsp k&nbsp ≤30)

输出数据

输出包含一行。在这一行中,应当包含两个整数x,y表示最优解的坐标,如果有多个最优解,那么输出x最小的,如果有x相同,那么输出y最小的。

样例输入

复制
5
2 3 5 3
2 1 100 30
2 2 1 1
3 2 7 6
1 1 4 30
 \n
 · · · \n
 · ·   ·  \n
 · · · \n
 · · · \n
 · · ·  \n

样例输出

复制
2 1
 · \n

提交

请先 登录

Source

某校NOIP模拟题

© 2024 FAQs Contact About