首页 > ACM题库 > HDU-杭电 > hdu 3384 Locate Mining Center待解决[解题报告]C++
2014
03-23

hdu 3384 Locate Mining Center待解决[解题报告]C++

Locate Mining Center

问题描述 :

As part of a peace treaty with the Navi, the humans are allowed mine for Unobtainium in a remote, deserted area of Pandora. The scientists have identified many possible excavation sites, and are now trying to figure out where to place the Mining Center. The placement of the mining center is further constrained by the fact that the robots that will carry the Unobtainium from the excavation sites to the mining center can only walk along prespecified Grid lines (see figure). The goal is now to find the location of the mining center so that the maximum distance to the excavation sites is minimized. You are to write a program for finding that location.

Specifically, you are given the x- and y-coordinates of the excavations sites, (x1, y1), (x2, y2), …(xn, yn) (n denotes the number of excavation sites). You are to find the coordinates for the Mining Center, (x0, y0), so that the maximum of the distances between the mining center and the excavation sites is minimized. All coordinates must be integers. The distance metric to be used is the rectilinear distance (also called Manhattan distance). Specifically, the rectilinear distance between (x0, y0) and (xi, yi) is:

|xi – x0| + |yi – y0|

Further, if there are multiple locations which qualify, then you must find the location that is closest to the origin by Euclidean distance q metric. Since origin is at (0, 0), this corresponds to minimizing .

In other words, given the input (x1, y1), …, (xn, yn), your goal is to find (x0, y0) such that:


is minimized, and if there are multiple answers, then is the smallest among all such answers.

输入:

The first line in the test data file contains the number of test cases, n. After that, each line contains one test case. The test case begins with the number of mines, followed by the x and y coordinates of each mine. All coordinates must be integers. Very large coordinate values may be used (million+), so brute force methods will not work.

输出:

The first line in the test data file contains the number of test cases, n. After that, each line contains one test case. The test case begins with the number of mines, followed by the x and y coordinates of each mine. All coordinates must be integers. Very large coordinate values may be used (million+), so brute force methods will not work.

样例输入:

2 
4 100 0 40 0 -10 0 20 0 
3 245 692 -772 -647 330 526

样例输出:

LOCATION 45 0
LOCATION -121 -120


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  5. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c