Codevs2490 导弹防御塔

2490 导弹防御塔

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 大师 Master

题目描述 Description

　　Freda的城堡——
　　“Freda，城堡外发现了一些入侵者！”
　　“喵...刚刚探究完了城堡建设的方案数，我要歇一会儿嘛lala~”
　　“可是入侵者已经接近城堡了呀！”
　　“别担心，rainbow，你看呢，这是我刚设计的导弹防御系统的说~”
　　“喂...别卖萌啊……”

　　Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。
　　所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
　　现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。

输入描述 Input Description

　　第一行五个正整数N,M,T1,T2,V。
　　接下来M行每行两个整数，代表入侵者的坐标。
　　接下来N行每行两个整数，代表防御塔的坐标。

输出描述 Output Description

　　输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。

样例输入 Sample Input

3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0

样例输出 Sample Output

91.500000

数据范围及提示 Data Size & Hint

　　对于40%的数据，N,M<=20.
　　对于100%的数据， 1≤N≤50, 1≤M≤50，坐标绝对值不超过10000，T1,T2,V不超过2000.

来源：Nescafe 19

【题解】

二分答案，让每个炮台发射尽量多的导弹，即把一个炮台拆成很多个点，

看每个点能不能打到某个入侵者，打到就往入侵者连边

注意二分上界

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cmath>
  6 #define max(a, b) ((a) > (b) ? (a) : (b))
  7 #define min(a, b) ((a) < (b) ? (a) : (b)) 
  8 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 
  9 
 10 const int INF = 0x3f3f3f3f;
 11 const double eps = 0.0000001;
 12 const int MAXN = 50 + 10;
 13 
 14 inline void read(int &x)
 15 {
 16     x = 0;char ch = getchar(), c = ch;
 17     while(ch < '0' || ch > '9')c = ch, ch = getchar();
 18     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 19     if(c == '-') x = -x;
 20 }
 21 
 22 int n,m,t1,t2;
 23 double v;
 24 int tax[MAXN],tay[MAXN],qinx[MAXN],qiny[MAXN];
 25 int g[100000][MAXN], lk[MAXN], b[MAXN];
 26 int tot;
 27 
 28 inline double dis(int a, int b)
 29 {
 30     return sqrt(abs(tax[a] - qinx[b]) * abs(tax[a] - qinx[b]) + abs(tay[a] - qiny[b]) * abs(tay[a] - qiny[b]));
 31 }
 32 
 33 //-1:> 0:= 1:< 
 34 int cmp(double a, double b)
 35 {
 36     if(abs(a - b) <= eps)return 0;
 37     return a - b < 0 ? 1 : -1;
 38 } 
 39 
 40 int dfs(int u)
 41 {
 42     for(register int i = 1;i <= m;++ i)
 43     {
 44         if(!b[i] && g[u][i])
 45         {
 46             b[i] = 1;
 47             if(lk[i] == -1 || dfs(lk[i]))
 48             {
 49                 lk[i] = u;
 50                 return 1;
 51             }
 52         }
 53     }
 54     return 0;
 55 }
 56 
 57 int xiongyali()
 58 {
 59     int ans = 0;
 60     memset(lk, -1, sizeof(lk));
 61     for(register int i = 1;i <= tot;++ i)
 62     {
 63         memset(b, 0, sizeof(b));
 64         ans += dfs(i);
 65     }
 66     return ans;
 67 }
 68 
 69 int check(double ma)
 70 {
 71     memset(g, 0, sizeof(g));
 72     tot = 0;
 73     //枚举炮台 
 74     for(register int i = 1;i <= n;++i)
 75     {
 76         //发射时间 
 77         for(register double now = t1;cmp(now, ma) != -1;now += t2 + t1)
 78         {
 79             ++ tot;
 80             //看能到达的入侵者 
 81             for(register int j = 1;j <= m;++ j)
 82             {
 83                 if(cmp(now + dis(i,j) / v, ma) != -1)
 84                     g[tot][j] = 1;
 85             }
 86         }
 87     }
 88     if(xiongyali() == m) return 1;
 89     return 0;
 90 }
 91 
 92 int main()
 93 {
 94     scanf("%d %d %d %d %lf", &n, &m, &t1, &t2, &v);
 95     t2 *= 60;v = v/60;
 96     for(register int i = 1;i <= m;++ i)
 97         scanf("%d %d", &qinx[i], &qiny[i]);
 98     for(register int j = 1;j <= n;++ j)
 99         scanf("%d %d", &tax[j], &tay[j]);
100     double l = 1, r = 1400000, mid, ans = 0;
101     while(cmp(l + eps, r) == 1)
102     {
103         mid = (l + r) / 2; 
104         if(check(mid))r = mid, ans = mid;
105         else l = mid;
106     } 
107     printf("%.6f", ans/60);
108     return 0;
109 }

Codevss2490

Codevs2490 导弹防御塔

2490 导弹防御塔

2490 导弹防御塔

相关推荐