#include "assert.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
// #include <math.h>
// #include <bits/stdc++.h>
// clang-format off
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// //map
// tree <int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> m;
// //multiset
// tree <pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> s;
// s.find_by_order();
// s.order_of_key(); //#strictly smaller.
template <typename T> ostream& operator<<(ostream& out, const vector<T>& vec) {
if (vec.empty()) { out << "{}"; return out; } out << '{';
for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
return out << vec.back() << '}'; }
template <typename T, size_t N> ostream& operator<<(ostream& out, const array<T, N>& vec) {
if (vec.empty()) { out << "{}"; return out; } out << '{';
for (int i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; }
return out << vec.back() << '}'; }
template <typename T> ostream& operator<<(ostream& out, const set<T>& set) {
out << '{'; for (auto it = set.begin(); it != set.end(); it++) {
T element = *it; out << element; if (std::next(it) != set.end()) {out << ", ";} }
return out << '}'; }
template <typename T> istream &operator>>(istream &in, vector<T> &a) {
for (int i = 0; i < a.size(); ++i) {
in >> a[i];
} return in; }
template <typename T, size_t N> istream &operator>>(istream &in, array<T, N> &a) {
for (int i = 0; i < N; ++i) {
in >> a[i];
} return in; }
template <typename T> T min(vector<T> &a) {
T ans = a[0];
for (int i = 1; i < a.size(); ++i) { if (a[i] < ans) { ans = a[i]; } } return ans; }
template <typename T> T max(vector<T> &a) {
T ans = a[0];
for (int i = 1; i < a.size(); ++i) { if (a[i] > ans) { ans = a[i]; } } return ans; }
#define FOR3(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define FOR2(i, a) for (int i=0; i<(signed)(a); i++)
#define GET_MACRO2(_1,_2,_3,NAME,...) NAME
#define FOR(...) GET_MACRO2(__VA_ARGS__, FOR3, FOR2)(__VA_ARGS__)
#define RFOR(i, b, a) for (int i=(b); i>=(signed)(a); i--)
#define dbg1(v) cerr << "L" << __LINE__ << "> " << #v << "=" << (v) << endl;
#define dbg2(x,y) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << endl;
#define dbg3(x,y,z) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << endl;
#define dbg4(x,y,z,w) cerr << "L" << __LINE__ << "> " << #x << "=" << (x) << ", " << #y << "=" << (y) << ", " << #z << "=" << (z) << ", " << #w << "=" << (w) << endl;
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define dbg(...) GET_MACRO(__VA_ARGS__, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#define ll long long
#define ar array
#define nl "\n"
using vi = vector<int>;
using vll = vector<ll>;
using ii = ar<int, 2>;
// clang-format on
// #ifdef LOCAL
// #include "algo/debug.h"
// #else
// #define debug(...) 42
// #endif
const int M = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const char dir[4] = {'U', 'R', 'D', 'L'};
const double eps = 1e-9;
auto xdiv = [](const ar<double, 2> &v1, const ar<double, 2> &v2) {
double x1 = v1[0], x2 = v2[0];
double r1 = v1[1], r2 = v2[1];
double z1 = 1 / sqrt(r1), z2 = 1 / sqrt(r2);
double y1 = x1 * z1, y2 = x2 * z2;
return (y2 - y1) / (z2 - z1);
};
vector<double> solve1(int n, vector<ar<double, 2>> &a) {
vector<ar<double, 2>> s; // x, r
vector<double> ans;
FOR(i, n) {
double x = a[i][0], r = a[i][1];
// cin >> x >> r;
if (s.size()) {
while (s.size() > 1 && x >= xdiv(*(s.rbegin() + 1), s.back())) {
s.pop_back();
}
double d = x - s.back()[0];
chmin(r, d * d / 4 / s.back()[1]);
while (s.size() > 0 && r >= s.back()[1] || s.size() > 1 && xdiv(*(s.rbegin() + 1), s.back()) <= xdiv(s.back(), {x, r})) {
s.pop_back();
}
}
s.push_back({x, r});
ans.push_back(r);
}
return ans;
}
vector<double> solve2(int n, vector<ar<double, 2>> &a) {
vector<double> ans(n);
FOR(i, n) {
double x = a[i][0], r = a[i][1];
FOR(j, 0, i - 1) {
double d = x - a[j][0];
chmin(r, d * d / 4 / ans[j]);
}
ans[i] = r;
}
return ans;
}
int main() {
#ifndef __APPLE__
// freopen("exercise.in", "r", stdin);
// freopen("exercise.out", "w", stdout);
#endif
// ifstream in("/Users/a/Downloads/test_input.txt");
// cin.rdbuf(in.rdbuf());
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<ar<double, 2>> a(n);
FOR(i, n) {
cin >> a[i][0] >> a[i][1];
}
auto ans = solve1(n, a);
FOR(i, n) {
cout << fixed << setprecision(3) << ans[i] << nl;
}
// random_device rd;
// mt19937 generator(rd());
// // uniform_int_distribution<int> dist(1, 100); // including both ends
// uniform_real_distribution<double> dist(1.0, 1000.0);
// FOR(T, 10000) {
// int n = 400;
// vector<ar<double, 2>> a(n);
// FOR(i, n) {
// a[i][0] = dist(generator);
// a[i][1] = 1e9;
// }
// sort(a.begin(), a.end());
// a[0][1] = 10;
// auto ans1 = solve1(n, a);
// auto ans2 = solve2(n, a);
// bool eq = true;
// FOR(i, n) {
// if (abs(ans1[i] - ans2[i]) > 1e-6) {
// eq = false;
// break;
// }
// }
// if (!eq) {
// dbg(T);
// dbg(a);
// dbg(ans1);
// dbg(ans2);
// break;
// }
// }
}
Compilation message
bal.cpp: In function 'std::vector<double> solve1(int, std::vector<std::array<double, 2> >&)':
bal.cpp:121:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
121 | while (s.size() > 0 && r >= s.back()[1] || s.size() > 1 && xdiv(*(s.rbegin() + 1), s.back()) <= xdiv(s.back(), {x, r})) {
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
10 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
2 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
505 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
2000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
1360 KB |
20000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
37 ms |
2820 KB |
50000 numbers |
| 2 |
Correct |
32 ms |
3032 KB |
49912 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
72 ms |
5060 KB |
100000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
5884 KB |
115362 numbers |
| 2 |
Correct |
81 ms |
6424 KB |
119971 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
108 ms |
7632 KB |
154271 numbers |
| 2 |
Correct |
122 ms |
10352 KB |
200000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
134 ms |
9440 KB |
200000 numbers |
| 2 |
Correct |
140 ms |
10352 KB |
199945 numbers |
