Phủ sóng

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 0.25s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Thầy Lê Minh Hoàng
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Dự kiến xây dựng mạng lưới phát thanh, truyền hình ở một địa phương nọ có một đài phát và trạm tiếp sóng đánh số từ ~1~ tới ~n~. Trạm thứ ~i~ đã được xây dựng ở toạ độ ~(x_{i}~, ~y_{i})~. Để đảm bảo tính trung thực của các nguồn tin, các trạm tiếp sóng chỉ có thể nhận tín hiệu trực tiếp từ đài phát. Và như vậy có nghĩa là để phát sóng đến tất cả các trạm thu, bán kính phủ sóng của đài phát phải đủ lớn để phủ hết các trạm tiếp sóng. (Giả sử vùng phủ sóng là hình tròn có tâm là đài phát).

Yêu cầu: Hãy tìm vị trí đặt đài phát sao cho khoảng cách từ trạm thu xa nhất tới đài phát là ngắn nhất. Cho biết bán kính phủ sóng trong phương án tìm được tối thiểu phải là bao nhiêu.

Input

  • Dòng đầu: Chứa số nguyên dương ~n~ ~(0 < n \le 200)~.
  • Dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~(x_i~, ~y_i)~ có giá trị tuyệt đối không quá ~10000~ cách nhau ít nhất một dấu cách.

Output

Ghi ra bán kính nhỏ nhất tìm được, làm tròn tới 6 chữ số sau dấu chấm thập phân.

Sample Input

8
0 0
200 300
200 0
200 200
0 200
100 300
300 100
100 0

Sample Output

182.107840

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    Keanloinoidoi  đã bình luận lúc 12, Tháng 2, 2025, 14:01

    DAY LA Y TUONG THUAT TOAN VA CODE CUA TOI BAI NAY DOI VOI TOI KHA EZ #include <iostream>

    include <iomanip>

    include <cmath>

    include <vector>

    include <limits>

    using namespace std;

    const double EPS = 1e-9;

    struct Point { double x, y; };

    struct Circle { Point c; double r; };

    double dist(const Point &a, const Point &b) { return sqrt((a.x-b.x)(a.x-b.x) + (a.y-b.y)(a.y-b.y)); }

    bool contains(const Circle &C, const Point &p) { return dist(C.c, p) <= C.r + EPS; }

    Circle circleFrom2Points(const Point &a, const Point &b) { Point c = {(a.x + b.x)/2.0, (a.y + b.y)/2.0}; double r = dist(a,b)/2.0; return {c, r}; }

    Circle circleFrom3Points(const Point &a, const Point &b, const Point &c) { double d = 2 * (a.x(b.y - c.y) + b.x(c.y - a.y) + c.x(a.y - b.y)); if(fabs(d) < EPS) return {{0,0}, numeric_limits<double>::infinity()}; double ax2ay2 = a.xa.x + a.ya.y; double bx2by2 = b.xb.x + b.yb.y; double cx2cy2 = c.xc.x + c.yc.y; Point center = { (ax2ay2(b.y - c.y) + bx2by2(c.y - a.y) + cx2cy2(a.y - b.y)) / d, (ax2ay2(c.x - b.x) + bx2by2(a.x - c.x) + cx2cy2*(b.x - a.x)) / d }; double r = dist(center, a); return {center, r}; }

    int main(){ int n; cin >> n; vector<Point> pts(n); for (int i = 0; i < n; i++){ cin >> pts[i].x >> pts[i].y; }

    if(n == 0) {
    cout << fixed << setprecision(6) << 0.000000;
    return 0;
}
if(n == 1){
    cout << fixed << setprecision(6) << 0.000000;
    return 0;
}

Circle minC = {{0,0}, numeric_limits<double>::infinity()};

// Try circle determined by 2 points
for (int i = 0; i < n; i++){
    for (int j = i+1; j < n; j++){
        Circle c = circleFrom2Points(pts[i], pts[j]);
        bool valid = true;
        for (int k = 0; k < n; k++){
            if (!contains(c, pts[k])){
                valid = false;
                break;
            }
        }
        if(valid && c.r < minC.r)
            minC = c;
    }
}

// Try circle determined by 3 points
for (int i = 0; i < n; i++){
    for (int j = i+1; j < n; j++){
        for (int k = j+1; k < n; k++){
            Circle c = circleFrom3Points(pts[i], pts[j], pts[k]);
            if(c.r == numeric_limits<double>::infinity()) continue;
            bool valid = true;
            for (int t = 0; t < n; t++){
                if(!contains(c, pts[t])){
                    valid = false;
                    break;
                }
            }
            if(valid && c.r < minC.r)
                minC = c;
        }
    }
}

cout << fixed << setprecision(6) << minC.r;
return 0;

    }