Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <math.h>
- #include <algorithm>
- #include <set>
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <map>
- #include <string>
- #include <time.h>
- #include <cassert>
- #include <functional>
- #include <memory.h>
- #include <stack>
- #include <bitset>
- #include <unordered_map>
- #include <unordered_set>
- #include <random>
- #include <chrono>
- #include <fstream>
- #include <climits>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef unsigned u;
- typedef long double ld;
- typedef vector<vector<int>> vvi;
- typedef unsigned char uc;
- typedef unsigned short us;
- #define mp(a, b) make_pair(a, b)
- #define pb(a) push_back(a)
- #define INF 1000000000
- #define LLINF 1000000000000000000LL
- #define EPS 1e-14l
- #define pii pair<int, int>
- #define puu pair<u, u>
- const char DEBUG = 0;
- mt19937 gen((u)chrono::high_resolution_clock::now().time_since_epoch().count());
- #pragma comment(linker, "/STACK:16777216")
- int pos[100000];
- int vel[100000];
- int n;
- ld get_dist(ld t)
- {
- ld min_x = -1;
- ld max_x = 0;
- for (int i = 0; i < n; i++)
- {
- ld x = pos[i] + vel[i] * t;
- if (min_x < 0 || min_x > x)
- min_x = x;
- max_x = max(max_x, x);
- }
- return max_x - min_x;
- }
- ld ternary(ld l, ld r)
- {
- while (r - l > 1e-13l)
- {
- ld m1 = l + (r - l) / 3;
- ld m2 = r - (r - l) / 3;
- ld d1 = get_dist(m1);
- ld d2 = get_dist(m2);
- if (d1 < d2)
- r = m2;
- else
- l = m1;
- }
- return (l + r) / 2;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for (int i = 0; i < n; i++)
- cin >> pos[i] >> vel[i];
- ld best_t = 0;
- int r = 10000000;
- ld prev_dist = get_dist(ternary(0, 1));
- for (int i = 1; i <= 10000000 / 2; i *= 2)
- {
- ld cur_dist = get_dist(ternary(i, 2 * i));
- if (prev_dist < cur_dist + 1e-6)
- {
- r = i;
- break;
- }
- prev_dist = cur_dist;
- }
- best_t = ternary(r / 2, r);
- cout.precision(8);
- cout << fixed << best_t << " " << get_dist(best_t);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement