島嶼渡假↘下殺$4900起工程師靠存股年領百萬股息攝影界美人正妹指定相機款老伯送飲料 遭學生糾察...
2013-07-12 16:28:17 人氣(49) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][最鄰近點] 10750 - Beautiful Points

0
收藏
0
推薦

Beautiful Points

Time limit: ? seconds
Memory limit: 64 megabytes

There are several points on the plane named beauty points. Given a point A, its ugliness is defined as |AB|+|AC|, where B and C are two beauty points nearest to A.

Your task is: given beauty points, find the most beautiful point, i.e., the point having least ugliness. Note: the most beautiful point doesn't have to be a beauty point.

Input

The first line of the input contains the number of the test cases, which is at most 10. The descriptions of the test cases follow. The first line of a test case descriptions contains an integer N (2 ≤ N ≤ 10000), which is the number of beauty points. Each of the next N lines contains two integers X and Y separated by a space (-10000 ≤ X, Y ≤ 10000) being the coordinates of a beauty point. No two beauty points in a test case description have the same coordinates. The test cases are separated by blank lines.

Output

For each test case in the input, output the coordinates of any most beautiful point separated by a space, with at least three digits after the decimal point. Print a blank line between test cases.

Examples

InputOutput
2

4
0 0
0 1
1 1
1 0

4
-1 -1
0 0
1 0
2 1
0.500 0.000

0.500 0.000

題目是要找到平面上一點到給定的其中最近兩點距離最小。
很簡單地會想到兩點的中點,因此找最鄰近點對的中點。

用 D&C 分治的想法去解。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
int mndist;
Pt D[10005];
double px, py;
void merge(int l, int r) {
    if(l >= r)  return;
    int i, j, m;
    m = (l+r)/2;
    merge(l, m);
    merge(m+1, r);
    for(i = m; i >= l; i--) {
        if((D[i].x-D[m].x)*(D[i].x-D[m].x) >= mndist)
            break;
        for(j = m+1; j <= r; j++) {
            if((D[i].x-D[j].x)*(D[i].x-D[j].x) >= mndist)
                break;
            int v = (D[i].x-D[j].x)*(D[i].x-D[j].x)+(D[i].y-D[j].y)*(D[i].y-D[j].y);
            if(v < mndist) {
                mndist = v;
                px = (D[i].x+D[j].x)/2.0;
                py = (D[i].y+D[j].y)/2.0;
            }
        }
    }
}
int main() {
    int testcase, n, i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        sort(D, D+n);
        mndist = 0xfffffff;
        merge(0, n-1);
        printf("%.3lf %.3lf\n", px, py);
        if(testcase)    puts("");
    }
    return 0;
}

10750Beautiful PointsD&C鄰近點對
台長:Morris
人氣(49) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10710 - Chinese Shuffle
此分類上一篇:[UVA][dp] 10723 - Cyborg Genes

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文