Một quốc gia đang thử nghiệm hệ thống phòng thủ tên lửa gồm 2 trạm. Mỗi trạm có thể điều chỉnh bán kính hoạt động để bao phủ các tên lửa bay qua. Chi phí vận hành hàng ngày được tính bằng tổng bình phương bán kính của hai trạm. Nhiệm vụ là tìm cách phân bổ bán kính sao cho toàn bộ tên lửa được chặn với chi phí thấp nhất.

Đầu vào

• Hai tọa độ đầu tiên: (x1,y1) và (x2,y2) - vị trí các trạm
• Số nguyên N: số lượng tên lửa
• N cặp tọa độ (xi,yi) mô tả vị trí tên lửa

Đầu ra

Tổng giá trị nhỏ nhất của r1² + r2²

Ví dụ

0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1

Kết quả: 30

Giải pháp

Phương pháp giải quyết dựa trên sắp xếp và theo dõi giá trị tối ưu. Các bước chính:

1. Tính khoảng cách bình phương từ mỗi tên lửa đến cả hai trạm
2. Sắp xếp tên lửa theo khoảng cách đến trạm 1 theo thứ tự giảm dần
3. Duyệt danh sách đã sắp xếp để tìm tổ hợp bán kính tối ưu

Thực hiện bằng C

#include <stdio.h>
#include <stdlib.h>

#define MAX_MISSILES 100000

typedef struct {
    int distA;
    int distB;
} MissileData;

int readInteger() {
    int value = 0, sign = 1;
    char ch;
    while (!isdigit(ch = getchar()) && ch != '-');
    if (ch == '-') sign = -1, ch = getchar();
    while (isdigit(ch)) {
        value = value * 10 + (ch - '0');
        ch = getchar();
    }
    return value * sign;
}

int compareDesc(const void *a, const void *b) {
    return ((MissileData*)b)->distA - ((MissileData*)a)->distA;
}

int main() {
    int x1 = readInteger(), y1 = readInteger();
    int x2 = readInteger(), y2 = readInteger();
    int n = readInteger();
    MissileData missiles[MAX_MISSILES];
    
    for(int i=0; i<n; i++) {
        int x = readInteger(), y = readInteger();
        missiles[i].distA = (x-x1)*(x-x1) + (y-y1)*(y-y1);
        missiles[i].distB = (x-x2)*(x-x2) + (y-y2)*(y-y2);
    }
    
    qsort(missiles, n, sizeof(MissileData), compareDesc);
    
    int totalCost = missiles[0].distA;
    int maxB = missiles[0].distB;
    
    for(int i=1; i<n; i++) {
        totalCost = fmin(totalCost, missiles[i].distA + maxB);
        maxB = fmax(maxB, missiles[i].distB);
    }
    
    printf("%d\n", totalCost);
    return 0;
}

Thực hiện bằng C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_SIZE = 1e5+5;

struct Missile {
    int range1;
    int range2;
};

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n; cin >> n;
    vector<Missile> data(n);
    
    for(auto &m : data) {
        int x, y; cin >> x >> y;
        m.range1 = (x-x1)*(x-x1) + (y-y1)*(y-y1);
        m.range2 = (x-x2)*(x-x2) + (y-y2)*(y-y2);
    }
    
    sort(data.begin(), data.end(), [](Missile a, Missile b) {
        return a.range1 > b.range1;
    });
    
    int minCost = data[0].range1;
    int maxSecond = data[0].range2;
    
    for(int i=1; i<n; ++i) {
        minCost = min(minCost, data[i].range1 + maxSecond);
        maxSecond = max(maxSecond, data[i].range2);
    }
    
    cout << minCost << endl;
    return 0;
}