Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:32000000")
- #pragma GCC optimize("O3")
- #include <stdio.h>
- #include <string.h>
- #include <memory.h>
- #include <stdlib.h>
- #include <iostream>
- #include <time.h>
- #include <algorithm>
- #include <math.h>
- #include <vector>
- #include <set>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <fstream>
- #include <map>
- #include <unordered_map>
- #include <deque>
- using namespace std;
- #define inf 1000000007
- #define eps 1e-7
- #define mp(a, b) make_pair(a, b)
- #define llinf 2000000000000000008LL
- typedef long long ll;
- typedef unsigned u;
- typedef long double ld;
- typedef unsigned char uc;
- typedef unsigned long long ull;
- int n;
- int x[100005];
- int v[100005];
- long double f(long double t) {
- long double mn = llinf, mx = -llinf;
- for (int i = 0; i < n; i++) {
- long double now = 1.0 * x[i] + 1.0 * v[i] * t;
- mn = min(mn, now);
- mx = max(mx, now);
- }
- return mx - mn;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin.sync_with_stdio(0);
- cout.sync_with_stdio(0);
- cout.precision(8);
- srand(time(0));
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> x[i] >> v[i];
- }
- long double l = 0, r = llinf;
- for (int i = 0; i < 400; i++) {
- long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
- if (f(m1) > f(m2)) {
- l = m1;
- }
- else {
- r = m2;
- }
- }
- cout << fixed << r << " " << f(r);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement