#include #include #include #include #include //makro na spočtení vzdálenosti dvou bodů typu Bod #define DIST(p,q) sqrt((p.x - q.x)*(p.x - q.x) \ + (p.y - q.y)*(p.y - q.y)) //vrátí bod, který je středem úsečky mezi body a, b #define STRED(a,b) Bod((a.x + b.x) / 2, \ (a.y + b.y) / 2) //konstanta určující přesnost výpočtů #define EPSILON 1e-7 using namespace std; //struktura na uložení bodu struct Bod { double x, y; Bod() {} Bod(double _x, double _y) { x = _x; y = _y; } }; //struktura na uložení kruhu struct Kruh { double r; Bod S; Kruh() {} Kruh(Bod _S, double _r) { S = _S; r = _r; } }; //opíše kruh množině bodů o velikosti max. 3 Kruh opisKruh(vector body) { if (body.size() == 0) //0 bodů => žádný kruh return Kruh(Bod(0,0),-1); else if (body.size() == 1) //1 bod => poloměr 0 return Kruh(body.front(),0); else if (body.size() == 2) { //2 body Bod d = body.front(); Bod e = body.back(); //poloměr je polovina vzdálenosti double r = DIST(d,e)/2.0; //střed je střed úsečky Bod S = STRED(d,e); return Kruh(S, r); } else { //3 body Bod a = body[0]; Bod b = body[1]; Bod c = body[2]; //vzdálenosti bodů double dab = DIST(a,b); double dbc = DIST(b,c); double dac = DIST(a,c); Bod d, e; bool shodne = false; //nejsou mezi body 2 skoro shodné? if (dab < EPSILON && dab > -EPSILON) { shodne = true; d = a; e = c; } else if (dbc < EPSILON && dbc > -EPSILON) { shodne = true; d = a; e = c; } else if (dac < EPSILON && dac > -EPSILON) { shodne = true; d = a; e = b; } if (shodne) { //2 z bodů jsou shodné //opiš kruh jednomu z těch shodných //a třetímu bodu (3 shodné => r=0) double r = DIST(d,e)/2; Bod S = STRED(d,e); return Kruh(S, r); } //opisujeme kružinici 3 bodům Bod ab = STRED(a,b);//střed úsečky ab Bod bc = STRED(b,c);//střed úsečky bc //směrové vektory os úsekček ab a bc //pro jednoduchost reprezentované typem Bod Bod smer_ab = Bod(a.y - b.y, b.x - a.x); Bod smer_bc = Bod(b.y - c.y, c.x - b.x); //je třeba spočíst průnik těchto vektorů bool rovn = false;//osy jsou rovnoběžné if (smer_bc.x < EPSILON && smer_bc.x > -EPSILON) { if (smer_ab.x < EPSILON && smer_ab.x > -EPSILON) rovn = true;//obě osy rovnoběžné s y else {//osa bc rovnoběžná s y //nutno prohodit osy kvůli dělení 0 Bod tmp = ab; ab = bc; bc = tmp; tmp = smer_bc; smer_bc = smer_ab; smer_ab = tmp; } } //průnik vektorů se spočte pomocí rovnice: //S = ab + t * smer_ab = bc + u * smer_bc //vyjádříme si t, ale postupně, kvůli děl. 0 double s = smer_ab.y - smer_ab.x * smer_bc.y / smer_bc.x; //osy jsou rovnoběžné if ((s < EPSILON && s > -EPSILON) || rovn) { //najdi 2 nejvzdálenější body if (dab > dbc && dab > dac) { d = a; e = b; } else if (dbc > dab && dbc > dac) { d = b; e = c; } else if (dac > dab && dac > dbc) { d = a; e = c; } //opiš jim kružnici double r = DIST(d,e)/2; Bod S = STRED(d,e); return Kruh(S, r); } //výpočet t double t = (bc.y - ab.y + (ab.x - bc.x) * smer_bc.y / smer_bc.x) / s; //střed kružnice opsané: S = AB + t*smer_ab Bod S = Bod(ab.x + t * smer_ab.x, ab.y + t * smer_ab.y); double r = DIST(S,a); return Kruh(S,r); } } //rekurzivní funkce na spočtení nejmenšího kruhu //M je pole bodů, které musí ležet uvnitř kruhu //O je pole bodů, jež musí ležet na obvodu Kruh nejmensiKruh(vector M, vector O) { //je-li M prázdná nebo O obsahuje 3 body, //lze spočíst kruh přímo z bodů v O if (M.size() == 0 || O.size() == 3) { return opisKruh(O); } else { //spočti nejmenší kruh pro M bez bodu b Bod b = M.back(); M.pop_back(); Kruh K = nejmensiKruh(M, O); //náleží b do kruhu pro M bez bodu b? if (DIST(K.S, b) > K.r + EPSILON) { //bod b bude určitě ležet na obvodu O.push_back(b); K = nejmensiKruh(M, O); } return K; } } int main(void) { //načtení vstupu int n; scanf("%d", &n); double x, y; vector body; for (int i = 0; i < n; i++) { scanf("%lf%lf", &x, &y); //přidej bod do pole bodů body.push_back(Bod(x, y)); } Kruh K; if (n <= 2) //pro 2 body stačí opsat kruh K = opisKruh(body); else { //náhodně promíchej pole bodů random_shuffle(body.begin(), body.end()); //body na obvodu, zatím tam není žádný vector O; K = nejmensiKruh(body, O); } printf("Střed [%.4lf, %.4lf], poloměr %.4lf\n", K.S.x, K.S.y, K.r); return 0; }