fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <cstdio>
  5.  
  6. #define infinity 1000000000
  7. using namespace std;
  8.  
  9. typedef pair<double,double> interval;
  10.  
  11. int n;
  12.  
  13. double dist2(double x, double y){
  14.        return sqrt(x*x+y*y);
  15. }
  16.  
  17. double startx,starty;
  18.  
  19. // Returns the intersection of two intervals. isempty returns false if the intersection is empty
  20. interval intersection(interval i, interval j, bool& isempty){
  21.          interval k;
  22.          k.first = max(i.first, j.first);
  23.          k.second = min(i.second, j.second);
  24.          if (k.first > k.second) isempty = true;
  25.          return k;
  26. }
  27.  
  28. // Returns the distance between (px,py) and (vx,vy) or -1 if vx is not contained in curr
  29. double in_intersection(interval curr_i,double vx, double vy,double px,double py){
  30.        if (vx < curr_i.first or vx > curr_i.second) return -1;
  31.        return dist2(vx-px,vy-py);
  32. }
  33.  
  34. // What is the minimum distance from (px,py) to the goal(curr_i,vy) in a straight line?
  35. double reach_goal(interval curr_i, double vy, double px, double py){
  36.        double distmin = infinity;
  37.        double d1,d2,d3;
  38.        d1 = in_intersection(curr_i,curr_i.first,vy,startx,starty);
  39.        d2 = in_intersection(curr_i,curr_i.second,vy,startx,starty);
  40.        d3 = in_intersection(curr_i,startx,vy,startx,starty);
  41.        if (d1 > -0.5) distmin = min(distmin, d1);
  42.        if (d2 > -0.5) distmin = min(distmin, d2);
  43.        if (d3 > -0.5) distmin = min(distmin, d3);
  44.        return distmin;
  45. }
  46.  
  47.  
  48. // Distance between endpoints. -1 if it is not possible to reach it
  49. double dist[1000][2][1000][2];
  50.  
  51. int main(){
  52.     int t;
  53.     cin>>t;
  54.     while (t--){
  55.           int n;
  56.           cin>>n;
  57.           vector<pair<double,double> > vx;
  58.           vector<double> vy;
  59.           cin >> startx >> starty;
  60.           for (int i=0;i<n;i++){
  61.               double a,b,c;
  62.               cin >> c >> a >> b;
  63.               vx.push_back(make_pair(a,b));
  64.               vy.push_back(c);
  65.           }
  66.           // Can I reach the i-th endpoint from the start in a straight line?
  67.           // -1 for not reaching, != -1 with the distance
  68.           double achieve_start[n][2];
  69.           // Can I reach the goal from the i-th endpoint in a straight line?
  70.           // -1 for not reaching, != -1 with the distance
  71.           double achieve_goal[n][2];
  72.           // Best path from the start to the gate, possibly zigzagging
  73.           double dp[n][2];
  74.           // Initialization
  75.           for (int i=0;i<n;i++) for (int j=0;j<2;j++) for (int k=0;k<n;k++) for (int l=0;l<2;l++) dist[i][j][k][l]=-1;
  76.           for (int i=0;i<n;i++) achieve_start[i][0] = achieve_start[i][1] = achieve_goal[i][0] = achieve_goal[i][1] = -1;
  77.  
  78.           double distmin = infinity;
  79.           // We calculate the points reachable from the starting point
  80.           interval curr_i = vx[0];
  81.           double curr_y = vy[0];
  82.           achieve_start[0][0] = dist2(startx-vx[0].first,starty-vy[0]);
  83.           achieve_start[0][1] = dist2(startx-vx[0].second,starty-vy[0]);
  84.           for (int i=1;i<n;i++){
  85.               // We calculate the interval that we can reach in a straight line
  86.               curr_i.first = startx + (curr_i.first - startx)*(starty-vy[i]) / (starty-curr_y);
  87.               curr_i.second = startx + (curr_i.second - startx)*(starty-vy[i]) / (starty-curr_y);
  88.               curr_y = vy[i];
  89.               bool empty = false;
  90.               curr_i = intersection(curr_i,vx[i],empty);
  91.               if (empty) break;
  92.               achieve_start[i][0] = in_intersection(curr_i,vx[i].first,vy[i],startx,starty);
  93.               achieve_start[i][1] = in_intersection(curr_i,vx[i].second,vy[i],startx,starty);
  94.               if (i == n-1){
  95.                  // We can reach the goal from the start
  96.                  distmin = reach_goal(curr_i,vy[n-1],startx,starty);
  97.               }
  98.           }
  99.           // Very important. Don't forget this special case.
  100.           if (n == 1){
  101.              distmin = min(distmin,reach_goal(vx[0],vy[0],startx,starty));
  102.           }
  103.           // Distance between endpoints of the gates and gate->end
  104.           for (int i=0;i<n-1;i++){
  105.               for (int j=0;j<2;j++){
  106.                   if (j == 0) startx = vx[i].first; else startx = vx[i].second;
  107.                   starty = vy[i];
  108.                   interval curr_i = vx[i+1];
  109.                   double curr_y = vy[i+1];
  110.                   dist[i][j][i+1][0] = dist2(startx-vx[i+1].first,starty-vy[i+1]);
  111.                   dist[i][j][i+1][1] = dist2(startx-vx[i+1].second,starty-vy[i+1]);
  112.                   for (int k=i+1;k<n;k++){
  113.                       curr_i.first = startx + (curr_i.first - startx)*(starty-vy[k]) / (starty-curr_y);
  114.                       curr_i.second = startx + (curr_i.second - startx)*(starty-vy[k]) / (starty-curr_y);
  115.                       curr_y = vy[k];
  116.                       bool empty = false;
  117.                       curr_i = intersection(curr_i,vx[k],empty);
  118.                       if (empty) break;
  119.                       dist[i][j][k][0] = in_intersection(curr_i,vx[k].first,vy[k],startx,starty);
  120.                       dist[i][j][k][1] = in_intersection(curr_i,vx[k].second,vy[k],startx,starty);
  121.                       if (k == n-1){
  122.                          // We can reach the goal (last interval) straight from this point
  123.                          achieve_goal[i][j] = reach_goal(curr_i,vy[n-1],startx,starty);
  124.                       }
  125.                   }
  126.               }
  127.           }
  128.  
  129.           for (int i=0;i<n;i++) for (int j=0;j<2;j++) dp[i][j] = infinity;
  130.  
  131.           // min distance from the start in a straight line
  132.           for (int i=0;i<n;i++) for (int j=0;j<2;j++){
  133.               if (achieve_start[i][j] > -0.5) dp[i][j] = achieve_start[i][j];
  134.           }
  135.  
  136.           // DP: min. distance from the start possibly zigzagging
  137.           for (int i=0;i<n;i++){
  138.               for (int j=0;j<2;j++){
  139.                   for (int k=0;k<i;k++){
  140.                       for (int l=0;l<2;l++){
  141.                           if (dist[k][l][i][j] > -0.5){
  142.                              dp[i][j] = min(dp[i][j], dp[k][l] + dist[k][l][i][j]);
  143.                           }
  144.                       }
  145.                   }
  146.               }
  147.           }
  148.  
  149.           // We search over the minimum of the sum start->gate + gate->end
  150.           for (int i=0;i<n;i++){
  151.               for (int j=0;j<2;j++){
  152.                   if (achieve_goal[i][j] > -0.5){
  153.                      distmin = min(distmin, achieve_goal[i][j] + dp[i][j]);
  154.                   }
  155.               }
  156.           }
  157.           printf("%.6lf\n", distmin);
  158.     }
  159.     return 0;
  160. }
Runtime error #stdin #stdout 0s 34720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QN42xp
language:
C++ (gcc 8.3)
created:
8 years 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!