fork download
copy 
  1. /* longhoang08 */
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define maxn 200010
  5. #define cmax 1000000007
  6. #define llmax (1LL << 61)
  7. #define el '\n'
  8. #define pb push_back
  9. #define mp make_pair
  10. #define getbit(s,i) ((s>>(i-1))&1)
  11. #define bug(X) { cerr << #X << " = " << (X) << endl; }
  12. #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)
  13. #define For(i,a,b) for(int i = a; i <= b; i++)
  14. #define Ford(i,a,b) for(int i = a; i >= b; i--)
  15. #define Forv(i,v) for(int i = 0, _v = v.size(); i < _v; i++)
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair<int, int> ptq;
  21. typedef long double db;
  22. typedef pair<db, db> pdb;
  23.  
  24. int n, m, L;
  25. ptq a[maxn];
  26.  
  27. bool check(db x)
  28. {
  29.     vector <pdb> v;
  30.     For(i,2,m)
  31.     {
  32.         if (a[i].second > a[i-1].second)
  33.         {
  34.             if (x > a[i].second) v.pb(mp(a[i].first,a[i].second));
  35.             else if (x < a[i-1].second) continue;
  36.             else
  37.             {
  38.                 db x1 = a[i].second - a[i-1].second;
  39.                 db x2 = x - a[i-1].second;
  40.                 db y1 = a[i].first - a[i-1].first;
  41.                 db res = a[i-1].first + y1 * (x2/x1);
  42.                 v.pb(mp(res, x));
  43.             }
  44.         }
  45.         else
  46.         {
  47.             if (x > a[i-1].second || x < a[i].second) continue;
  48.             db x1 = x - a[i].second;
  49.             db x2 = a[i-1].second - a[i].second;
  50.             db y2 = a[i].first - a[i-1].first;
  51.             db y1 = (x1/x2) * y2;
  52.             v.pb(mp(a[i].first - y1, x));
  53.         }
  54.     }
  55.     db last = 0, prelast = -1;
  56.     int lamp = L;
  57.     int sz = v.size();
  58.     For(i,0,sz-1)
  59.     {
  60.         auto temp = v[i];
  61.         db l = max(db(0), temp.first - temp.second);
  62.         db r = min(db(n), temp.first + temp.second);
  63.         if (l <= last) prelast = max(prelast, r);
  64.         bool ok = true;
  65.         if (i < sz - 1)
  66.         {
  67.             db l1 = max(db(0), v[i+1].first - temp.second);
  68.             if (l1 <= last) ok = false;
  69.         }
  70.         if (ok)
  71.         {
  72.             lamp--;
  73.             last = prelast;
  74.             prelast = -1;
  75.         }
  76.         if (lamp == 0 || last == n) break;
  77.     }
  78.     if (last < n) return false;
  79.     return true;
  80. }
  81.  
  82. void solve()
  83. {
  84.     db first = 0, last = 1000000000, res = -1;
  85.     //cout << check(2.5) << ' ' << "OK" << endl;
  86.     //return;
  87.     For(ib,1,50)
  88.     {
  89.         db mid = (first + last)/2;
  90.         if (check(mid))
  91.         {
  92.             res = mid;
  93.             last = mid;
  94.         }
  95.         else first = mid;
  96.     }
  97.     if (res == -1)
  98.     {
  99.         cout << -1 << endl;
  100.         return;
  101.     }
  102.     For(i,1,2)
  103.     {
  104.         db temp = i * res;
  105.         long long t1 = round(temp);
  106.         if ( abs(t1 - temp) <= 0.001)
  107.         {
  108.             cout << t1 << ' ' << i << endl;
  109.             return;
  110.         }
  111.     }
  112.     cout << -1 << endl;
  113. }
  114.  
  115. int32_t main(int argc, char** argv)
  116. {
  117.     setbuf(stdout, NULL);
  118. 	int T, test_case;
  119. 	cin >> T;
  120. 	for(test_case = 0; test_case  < T; test_case++)
  121. 	{
  122. 	    cin >> n >> m >> L;
  123. 	    m++;
  124. 		cout << "Case #" << test_case+1 << endl;
  125. 		For(i,1,m)
  126. 		{
  127.             cin >> a[i].first >> a[i].second;
  128. 		}
  129. 		solve();
  130. 	}
  131.  
  132. 	return 0;
  133. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
1
8 4 1
0 1
4 5
8 1
15 8
20 3

8 2 2
0 1
4 5
8 1
compilation info 
prog.cpp:115:9: error: first parameter of 'main' (argument count) must be of type 'int'
int32_t main(int argc, char** argv)
        ^
1 error generated.
stdout
copy 
Standard output is empty
https://ideone.com/6nuEXv
language:
C++14 (clang 8.0)
created:
5 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!