fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr double EPS = 1e-9;
  5. constexpr int MAX_ITER = 100;
  6.  
  7. int w, h, n, d;
  8. vector<double> a, p;
  9.  
  10. // 주어진 각 구간과 밀도에 대해 총 이동 거리 dx를 반환
  11. // K = p_i * sin(theta_i), target_dx는 이 segment에서 커버할 수평 거리
  12.  
  13. double compute_dx(double K, const vector<double>& heights, const vector<double>& density) {
  14.     double total_x = 0.0;
  15.     for (int i = 0; i < (int)heights.size(); ++i) {
  16.         double t = K / density[i];
  17.         if (t >= 1.0 - EPS) return 1e18;
  18.         double cos_theta = sqrt(1.0 - t * t);
  19.         total_x += heights[i] * (t / cos_theta);
  20.     }
  21.     return total_x;
  22. }
  23.  
  24. double compute_time(double K, const vector<double>& heights, const vector<double>& density) {
  25.     double total_time = 0.0;
  26.     for (int i = 0; i < (int)heights.size(); ++i) {
  27.         double t = K / density[i];
  28.         if (t >= 1.0 - EPS) return 1e18;
  29.         double cos_theta = sqrt(1.0 - t * t);
  30.         total_time += density[i] * (heights[i] / cos_theta);
  31.     }
  32.     return total_time;
  33. }
  34.  
  35. double solve_segment(double target_dx, const vector<double>& heights, const vector<double>& density) {
  36.     double lo = 0.0, hi = 1e4;
  37.     for (int iter = 0; iter < MAX_ITER; ++iter) {
  38.         double mid = (lo + hi) / 2.0;
  39.         double dx = compute_dx(mid, heights, density);
  40.         if (dx < target_dx - EPS)
  41.             lo = mid;
  42.         else
  43.             hi = mid;
  44.     }
  45.     return compute_time(lo, heights, density);
  46. }
  47.  
  48. int find_lane(double y) {
  49.     if (y < EPS) return 1;
  50.     for (int i = 0; i < n; ++i) {
  51.         if (y < a[i] - EPS) return i + 1;
  52.     }
  53.     return n;
  54. }
  55.  
  56. int main() {
  57.     cin >> w >> h;
  58.     cin >> n >> d;
  59.  
  60.     a.resize(n);
  61.     for (int i = 0; i < n; ++i) cin >> a[i];
  62.     p.resize(n);
  63.     for (int i = 0; i < n; ++i) cin >> p[i];
  64.  
  65.     int k = find_lane(d);
  66.     double min_time = 1e18;
  67.  
  68.     for (int j = k; j <= n; ++j) {
  69.         vector<double> up_heights;
  70.         double prev = 0.0;
  71.         for (int i = 0; i < j - 1; ++i) {
  72.             up_heights.push_back(a[i] - prev);
  73.             prev = a[i];
  74.         }
  75.         if (j == 1) up_heights.push_back(d);
  76.         else up_heights.push_back(a[j - 1] - prev);
  77.         vector<double> up_density(p.begin(), p.begin() + j);
  78.  
  79.         if (j == k) {
  80.             double t = solve_segment(w, up_heights, up_density);
  81.             min_time = min(min_time, t);
  82.             continue;
  83.         }
  84.  
  85.         vector<double> down_heights;
  86.         prev = a[j - 1];
  87.         for (int i = j - 1; i >= k; --i) {
  88.             double bottom = (i == 0 ? 0.0 : a[i - 1]);
  89.             double hgt = prev - (i == k - 1 ? d : bottom);
  90.             down_heights.push_back(hgt);
  91.             prev = (i == k - 1 ? d : bottom);
  92.         }
  93.         vector<double> down_density(p.begin() + k - 1, p.begin() + j);
  94.         reverse(down_heights.begin(), down_heights.end());
  95.         reverse(down_density.begin(), down_density.end());
  96.  
  97.         // x 를 이분 탐색: up 에서 x 이동, down 에서 w - x 이동
  98.         double lo = 0.0, hi = w;
  99.         for (int it = 0; it < MAX_ITER; ++it) {
  100.             double mid = (lo + hi) / 2.0;
  101.             double up_t = solve_segment(mid, up_heights, up_density);
  102.             double down_t = solve_segment(w - mid, down_heights, down_density);
  103.             double up_t2 = solve_segment(mid + EPS, up_heights, up_density);
  104.             double down_t2 = solve_segment(w - mid - EPS, down_heights, down_density);
  105.  
  106.             if (up_t2 + down_t2 < up_t + down_t)
  107.                 lo = mid;
  108.             else
  109.                 hi = mid;
  110.         }
  111.         double mid = (lo + hi) / 2.0;
  112.         double total = solve_segment(mid, up_heights, up_density) +
  113.                        solve_segment(w - mid, down_heights, down_density);
  114.         min_time = min(min_time, total);
  115.     }
  116.  
  117.     cout << fixed << setprecision(10) << min_time << "\n";
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
25 10
2 4
8 10
5 3
stdout
copy 
108.2431940490
https://ideone.com/3jQgpS
language:
C++14 (gcc 8.3)
created:
14 days 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!