Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Mr. Macdonald is a farmer. He has a huge land to manage. To monitor the number of bugs in his land, he asks help from the famous professor T. Professor T is an expert on computer science.

Professor T studies several efficient approach and suggests Mr. Macdonald to setup a wireless sensor system in his land. The system will be setup as follows:

In each predened location, one wireless sensor will be established. Since all sensors are operated by batteries, the powers consumed by the sensors are determined by the eective com- munication distance (ECD) between sensors. Mr. Macdonald is a nice old man. He prefers not to trouble professor T much. Therefore, he decides that all sensors will be set in the same power level. That is, all sensors will have the same eective communication distance.

The land is so huge that it is not possible to cover all spots by the sensors. However, each sensor can broadcast the collected data to their neighbors as long as the neighbors are in its eective communication distance. But the total number of sensors is relative small comparing to the land. Mr. Macdonald needs to travel the whole land to collect the data from sensors everyday.

Mr. Macdonald is getting old. He hopes that the computer in his house can collect all data from all sensors automatically. Again, he called professor T for help. This time, professor T suggests Mr. Macdonald to setup a base station in his house. The house is right in the center of the land.

Due to the limited budget, the number of receiver/transmitter Mr. Macdonald can aord is limited and is relatively small comparing to the total number of sensors. It is impossible to assign receiver/transmitter to every sensor. Therefore, sensors with no receiver/transmitter need to send their data to the sensor with receiver/transmitter (directly or indirect) rst, After that, the sensor with receiver/transmitter sends all data it receives from other sensors along with the data it collects back to the base station. You may assume that the receiver/transmitter has enough power such that it always can send data back to the base station.

Professor T promises to write the necessary software to make all sensors work together in this way, but one important issue need to be studied. If all sensors are set at the maximum power level, all sensors might be able to send their data back without troubles, but the battery will be out-of-power soon. To save power, professor T need to decide the minimum power level needed such that the battery can have longest operating time while all sensor data can be col- lected by the base station.

Although professor T is good in programming, he is weak in algorithm design. Your goal is to help professor T to write a program to determine the minimum power level needed to set all sensors accordingly. To simplify our problem, please report the ECD corresponding to the minimum power level. Please apply the ceiling function to your answer.

Here is an example:

Assume that the land is 10×10 . There are three sensors, located at (1,1), (2,1) and (8,7). We also assume that there are 2 receiver/transmitters. In this example, the ECD of all sensors need to be set at 1.

Input 

The first line contains the number of test cases w , 1w10 . Then the w test cases are listed one by one. In each test case, the first line is a single integer, representing the number of receiver/transmitters for that test case. After that, the test case consists of some lines with two numbers each line:

X Y

Here two numbers are separated by a single blank, X is an integer, denoting the x-coordinate of the sensor, and Y is also an integer, denoting the y-coordinate of the same sensor. Each test case is ended by the following line: `-1'

Please note that the land is a rectangle with dimemsions 100000×100000 .

Output 

For each test case, output the corresponding ECD.

Sample Input 

1 
2 
1 1
2 1
8 7
-1

Sample Output 

1

---

題目描述：

地圖上有一些感測器，這些感測器如果都設定最大的傳輸功率，那麼電很快就耗盡，
因此希望能用最少的傳輸功率達到，傳輸功率等同歐幾理德距離，因此決定 r 是全部的傳輸功率，
等價於全部感測器都張出半徑 r 的圓。

此時至給予 w 個接收器，接收器負責將感測器的資料傳回去，但這裡不需要考慮接收器的能量消耗問題，
接收器可以直接從感測器中得到資料，又或者從感測器傳給感測器，間接地得到資料。

自己決定接收器的位置，問使用最少的 r，在最大接收器 w 個的限制時。

題目解法：

題目其實就是描述當給定一個半徑 r 時，給個感測器都會張出圓，
那有些感測器就可以形成區域的互聯，那只要連通元件個數 <= w 即可。

先將邊排序好(小->大)，使用並查集，依序納點，直到連通元件個數 <= w 就是答案。



#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int x[1000], y[1000];
struct E {
    int x, y;
    long long v;
    E(int a, int b, long long c):
        x(a), y(b), v(c) {}
    E():
        x(0), y(0), v(0) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[1000000];
int p[1000], rank[1000];
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int main() {
    int testcase;
    int i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, e;
        scanf("%d", &n);
        m = 0, e = 0;
        while(scanf("%d", &x[m]) == 1 && x[m] != -1)
            scanf("%d", &y[m]), m++;
        for(i = 0; i < m; i++)
            for(j = i+1; j < m; j++)
                D[e++] = E(i, j, ((long long)x[i]-x[j])*(x[i]-x[j])+((long long)y[i]-y[j])*(y[i]-y[j]));
        sort(D, D+e);
        for(i = 0; i < m; i++)
            p[i] = i, rank[i] = 1;
        int component = m;
        for(i = 0; i < e; i++) {
            if(joint(D[i].x, D[i].y))
                component--;
            if(component <= n) {
                printf("%.0lf\n", ceil(sqrt(D[i].v)));
                break;
            }
        }
    }
    return 0;
}