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;
}