列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

NPSC 2006 高中組 初賽 B.古力德

說明：給你幾個點的座標，請你算出可以涵蓋這些點的最小圓的半徑為多少。

解法：先取出三個點，以這三個點做出一個圓，如果這三個點形成一個銳角三角形，則這個圓就是它們的外接圓，而如果這三個點形成直角或鈍角三角形，則以最長邊為直徑做出這個圓。接下來每取出一個點，如果這個點在圓內，則不做處理，但如果這個點在圓外，則以這個點和原本三個點中的兩個點再做出一個圓，看是否可以涵蓋剩下的那個點。如此反覆，即可求出涵蓋所有點的最小圓。

參考程式：(By sagit)

代碼: [選擇]

// NPSC 2006 初賽 - 題目 B - 古力德 //
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

const double delta=0.0001;  // 浮點數誤差用
double cx, cy, cr;          // 圓心座標、半徑平方
double px[3], py[3];        // 三點的座標

// 使用 px[]、py[] 三點產生一個圓心為 (cx,cy) 半徑平方為 cr 的圓
void MakeCircle()
{
    int i;
    double dx[3], dy[3], r[3], a1, a2, b;
    dx[0]=px[1]-px[2], dy[0]=py[1]-py[2];
    dx[1]=px[0]-px[2], dy[1]=py[0]-py[2];
    dx[2]=px[0]-px[1], dy[2]=py[0]-py[1];
    // 計算三邊長的平方
    for (i=0; i<3; ++i)
        r[i]=dx[i]*dx[i]+dy[i]*dy[i];
    // 點 1,2 為長邊的鈍角三角形
    if ( r[0]>r[1]+r[2]-delta )
    {
        cx=(px[1]+px[2])/2.0;
        cy=(py[1]+py[2])/2.0;
        cr=r[0]/4.0;
    }
    // 點 0,2 為長邊的鈍角三角形
    else if ( r[1]>r[0]+r[2]-delta )
    {
        cx=(px[0]+px[2])/2.0;
        cy=(py[0]+py[2])/2.0;
        cr=r[1]/4.0;
    }
    // 點 1,2 為長邊的鈍角三角形
    else if ( r[2]>r[0]+r[1]-delta )
    {
        cx=(px[0]+px[1])/2.0;
        cy=(py[0]+py[1])/2.0;
        cr=r[2]/4.0;
    }
    // 銳角三角形
    else
    {
        a1=px[0]*px[0]-px[1]*px[1]+py[0]*py[0]-py[1]*py[1];
        a2=px[0]*px[0]-px[2]*px[2]+py[0]*py[0]-py[2]*py[2];
        b=dx[2]*dy[1]-dx[1]*dy[2];
        cx=(a1*dy[1]-a2*dy[2])/b/2.0;
        cy=(a2*dx[2]-a1*dx[1])/b/2.0;
        cr=(cx-px[0])*(cx-px[0])+(cy-py[0])*(cy-py[0]);
    }
}

int main()
{
    freopen("pb.in", "rt", stdin);
    freopen("pb.out", "w+t", stdout);
    int n, m, i, j;
    double x, y;

    while (1)
    {
        if (scanf("%d%d", &n, &m)<2) break;
        if ( n==0 ) break;
        scanf("%lf%lf", &cx, &cy);
        cr=0.0;
        for (i=0; i<3; i++)
            px[i]=cx, py[i]=cy;
        for (i=1; i<m; i++)
        {
            scanf("%lf%lf", &x, &y);
            // 檢查該點是否在圓內
            if ( (x-cx)*(x-cx)+(y-cy)*(y-cy)-delta < cr ) continue;
            for (j=0; j<3; j++)
            {
                // 將該點換入其中一個點
                swap(x, px[j]);
                swap(y, py[j]);
                // 產生新的圓
                MakeCircle();
                // 檢查新的圓是否涵蓋被換出去的那個點
                if ( (x-cx)*(x-cx)+(y-cy)*(y-cy)-delta < cr ) break;
            }
        }
        printf("%.3lf\n", sqrt(cr));
    }

//    system("PAUSE");
    return 0;
}

[sagit]

1.本解法不保證正確，歡迎各位提供正快速與正確的解法。

2.裁判測資第四組可能有誤，經我的程式和 tmt 的計算，
和原本裁判提供的解答差了 0.001 。

[lose]

輸入 :
500 5
0 0
2 0
1.3 1.48
1 -0.5
1.52 2.38
輸出應為:
1.471

你的程式碼卻跑出了 1.440 的答案,
如附圖
http://photo.pchome.com.tw/morris821028/133691198777