Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <cstdlib>
- #include <deque>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- using namespace std;
- typedef pair<int, int> pii;
- typedef pair<double, double> pdd;
- typedef long long li;
- typedef long double ld;
- #define forn(i,n) for(int (i) = 0; (i) < n; ++(i))
- #define EPS 1e-18
- bool zero(double x) {
- return abs(x) < EPS;
- }
- const double INF = 1e19;
- struct tp {
- int x, v;
- };
- bool operator < (const tp &a, const tp &b) {
- return a.x < b.x;
- }
- tp p[500500];
- int n;
- inline bool equal(double a, double b) {
- return b - a > -EPS;
- }
- bool f(double mid) {
- bool result = false;
- double maxx = -INF;
- for (int i = 0; i < n; i++) {
- double cur = (double)p[i].v * mid + p[i].x;
- if (p[i].v < 0) {
- if (equal(cur, maxx)) {
- result = true;
- break;
- }
- continue;
- }
- maxx = max(maxx, cur);
- }
- return result;
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- scanf("%d", &n);
- for (int i = 0; i < n; ++i)
- scanf("%d %d", &p[i].x, &p[i].v);
- sort(p, p + n);
- double ans = -1;
- double l = 0, r = 2e9;
- for (int i = 0; i < 100; ++i) {
- double mid = (l + r) / 2;
- if (f(mid))
- ans = mid, r = mid;
- else
- l = mid;
- }
- printf("%.18lf\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement