洛谷的[NOIP1999 普及组] 导弹拦截 解决程序

NOIP1999 普及组 导弹拦截 是一道经典的编程题目。

题目大意: 给定一个圆形的防御区域，和一些从外面向里面发射的导弹。你有一个导弹拦截系统，每次可以拦截一枚导弹，求最少几枚导弹可以拦截所有的导弹。

解决方法:

1. 输入边界值。

2. 建立一个数组，表示每枚导弹的位置和速度。

3. 对每枚导弹进行模拟，找到拦截的时间。

4. 按照拦截的时间从小到大排序，依次拦截导弹。

5. 输出最少拦截的导弹数量。

程序示例:

#include <stdio.h>
#include <math.h>

#define MAXN 1000
#define eps 1e-6

struct missile{
    double x, y, v;
}miss[MAXN];

double dist(double x1, double y1, double x2, double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main(){
    int n, r;
    scanf("%d%d", &n, &r);
    for (int i = 0; i < n; i++){
        scanf("%lf%lf%lf", &miss[i].x, &miss[i].y, &miss[i].v);
    }
    int ans = 0;
    while (1){
        double mint = 1e100;
        int minp = -1;
        for (int i = 0; i < n; i++){
            double t = dist(miss[i].x, miss[i].y, 0, 0) / miss[i].v;
            if (t < mint - eps){
                mint = t;
                minp = i;
            }
        }
        if (minp == -1) break;
        ans++;
        miss[minp].v = 0;
    }
    printf("%d\n", ans);
    return 0;
}