fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <queue>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <set>
  8. #include <deque>
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <math.h>
  12.  
  13. using namespace std;
  14.  
  15. const int MOD = 1000000007;
  16.  
  17. int res = 0;
  18. int N, M;
  19. int XX[100000];
  20. int LL[100000];
  21. int HH[100000];
  22.  
  23. void run()
  24. {
  25.     double length_fly = N;
  26.     for(int i = 0; i < M; ++i) {
  27.         scanf("%d%d%d", XX + i, LL + i, HH + i);
  28.     }
  29.     if(M == 0) {
  30.         printf("0\n");
  31.         return;
  32.     }
  33.     double xielv_l = -999999999999.0;
  34.     double xielv_h = 999999999999.0;
  35.     int l_idx = 0;
  36.     int h_idx = 0;
  37.     double cur_x = 0;
  38.     double cur_y = 0;
  39.  
  40.     for(int i = 0; i < M; ++i) {
  41.         double can_l = cur_y + xielv_l * (XX[i] - cur_x);
  42.         double can_h = cur_y + xielv_h * (XX[i] - cur_x);
  43.         if(can_l > LL[i]) {
  44.             double tmp_x = (XX[l_idx] - cur_x);
  45.             double tmp_y = (LL[l_idx] - cur_y);
  46.             tmp_x *= tmp_x;
  47.             tmp_y *= tmp_y;
  48.             length_fly -= sqrt(tmp_x + tmp_y);
  49.             cur_x = XX[l_idx];
  50.             cur_y = LL[l_idx];
  51.             if(length_fly < 0) {
  52.                 printf("%d\n", i);
  53.                 return;
  54.             }
  55.             i = l_idx;
  56.             h_idx = l_idx;
  57.             xielv_l = -999999999999.0;
  58.             xielv_h = 999999999999.0;
  59.         } else if(can_h < HH[i]) {
  60.             double tmp_x = (XX[h_idx] - cur_x);
  61.             double tmp_y = (HH[h_idx] - cur_y);
  62.             tmp_x *= tmp_x;
  63.             tmp_y *= tmp_y;
  64.             length_fly -= sqrt(tmp_x + tmp_y);
  65.             cur_x = XX[l_idx];
  66.             cur_y = HH[l_idx];
  67.             if(length_fly < 0) {
  68.                 printf("%d\n", i);
  69.                 return;
  70.             }
  71.             i = h_idx;
  72.             l_idx = h_idx;
  73.             xielv_l = -999999999999.0;
  74.             xielv_h = 999999999999.0;
  75.         }
  76.         if(can_l < LL[i]) {
  77.             double tmp_x = (XX[i] - cur_x);
  78.             double tmp_y = (LL[i] - cur_y);
  79.             tmp_x *= tmp_x;
  80.             tmp_y *= tmp_y;
  81.             if(length_fly <= sqrt(tmp_x + tmp_y)) {
  82.                 printf("%d\n", i);
  83.                 return;
  84.             }
  85.             l_idx = i;
  86.             xielv_l = (LL[i] - cur_y) / (XX[i] - cur_x);
  87.         }
  88.         if(can_h > HH[i]) {
  89.             double tmp_x = (XX[i] - cur_x);
  90.             double tmp_y = (HH[i] - cur_y);
  91.             tmp_x *= tmp_x;
  92.             tmp_y *= tmp_y;
  93.             if(length_fly <= sqrt(tmp_x + tmp_y)) {
  94.                 printf("%d\n", i);
  95.                 return;
  96.             }
  97.             h_idx = i;
  98.             xielv_h = (HH[i] - cur_y) / (XX[i] - cur_x);
  99.         }
  100.     }
  101.     printf("%d\n", M);
  102.     return;
  103. }
  104.  
  105. int main()
  106. {
  107.     while(~scanf("%d%d", &N, &M)) {
  108.         run();
  109.     }
  110.     return 0;
  111. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
9 3
2 2 4
4 1 2
6 6 7
stdout
copy 
2
https://ideone.com/qgAcRU
language:
C++14 (gcc 8.3)
created:
9 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!