fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. using namespace std;
  7.  
  8. struct Point {
  9.     double x, y;
  10.     Point() {}
  11.     Point(double x, double y) : x(x), y(y) {}
  12. };
  13.  
  14. double dist2(const Point& a, const Point& b) {
  15.     double dx = a.x - b.x;
  16.     double dy = a.y - b.y;
  17.     return dx * dx + dy * dy;
  18. }
  19.  
  20. int N, M, K;
  21. vector<Point> targets;      // 目标点
  22. vector<Point> deployments;  // 部署点
  23.  
  24. // 检查半径R是否可行
  25. bool check(double R) {
  26.     double R2 = R * R;
  27.     vector<int> cover(M, 0); // 每个部署点覆盖的目标点掩码
  28.     for (int j = 0; j < M; ++j) {
  29.         int mask = 0;
  30.         for (int i = 0; i < N; ++i) {
  31.             if (dist2(deployments[j], targets[i]) <= R2 + 1e-9) {
  32.                 mask |= (1 << i);
  33.             }
  34.         }
  35.         cover[j] = mask;
  36.     }
  37.  
  38.     const int INF = 1e9;
  39.     int full = (1 << N) - 1;
  40.     vector<int> dp(full + 1, INF);
  41.     dp[0] = 0;
  42.  
  43.     // 状态压缩DP，类似01背包
  44.     for (int j = 0; j < M; ++j) {
  45.         int mask = cover[j];
  46.         if (mask == 0) continue;
  47.         for (int s = full; s >= 0; --s) {
  48.             if (dp[s] < INF) {
  49.                 int ns = s | mask;
  50.                 if (dp[ns] > dp[s] + 1) {
  51.                     dp[ns] = dp[s] + 1;
  52.                 }
  53.             }
  54.         }
  55.     }
  56.     return dp[full] <= K;
  57. }
  58.  
  59. int main() {
  60.     ios::sync_with_stdio(false);
  61.     cin.tie(0);
  62.  
  63.     cin >> N >> M >> K;
  64.     targets.resize(N);
  65.     for (int i = 0; i < N; ++i) {
  66.         cin >> targets[i].x >> targets[i].y;
  67.     }
  68.     deployments.resize(M);
  69.     for (int j = 0; j < M; ++j) {
  70.         cin >> deployments[j].x >> deployments[j].y;
  71.     }
  72.  
  73.     // 计算二分上界：所有目标点到所有部署点的最大距离
  74.     double maxDist = 0;
  75.     for (int i = 0; i < N; ++i) {
  76.         for (int j = 0; j < M; ++j) {
  77.             double d = sqrt(dist2(targets[i], deployments[j]));
  78.             if (d > maxDist) maxDist = d;
  79.         }
  80.     }
  81.  
  82.     // 特殊情况：如果最大距离为0，直接输出0
  83.     if (maxDist < 1e-9) {
  84.         cout << fixed << setprecision(6) << 0.0 << endl;
  85.         return 0;
  86.     }
  87.  
  88.     // 二分半径R
  89.     double lo = 0, hi = maxDist;
  90.     for (int iter = 0; iter < 60; ++iter) {
  91.         double mid = (lo + hi) / 2;
  92.         if (check(mid)) {
  93.             hi = mid;
  94.         } else {
  95.             lo = mid;
  96.         }
  97.     }
  98.  
  99.     cout << fixed << setprecision(6) << hi << endl;
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3 3 2
3 4
3 1
5 4
1 1
2 2
3 3
stdout
copy 
2.236068
https://ideone.com/wXRxUt
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!