[problem:1388A]↵
↵
Idea: [user:Denisov,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388A]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while(q--){↵
int n; cin >> n;↵
if(n <= 30){↵
cout << "NO" << endl;↵
}↵
else{↵
cout << "YES" << endl;↵
if(n == 36 || n == 40 || n == 44){↵
cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl;↵
}↵
else{↵
cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl;↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388B]↵
↵
Idea: [user:Karavaev1101,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while (q--) {↵
int n; cin >> n;↵
int x = (n + 3) / 4;↵
for (int i = 0; i < n - x; ++i) {↵
cout << 9;↵
}↵
for (int i = 0; i < x; ++i) {↵
cout << 8;↵
}↵
cout << endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388C]↵
↵
Idea: [user:Karavaev1101,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388C]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 1e5 + 7;↵
↵
vector < int > gr[N];↵
↵
bool access = true;↵
↵
int p[N], h[N], a[N], g[N];↵
↵
void dfs(int v, int ancestor = -1) {↵
a[v] = p[v];↵
int sum_g = 0;↵
for (int to : gr[v]) {↵
if (to == ancestor) continue;↵
dfs(to, v);↵
sum_g += g[to];↵
a[v] += a[to];↵
}↵
if ((a[v] + h[v]) % 2 == 0) {} // first↵
else access = false;↵
g[v] = (a[v] + h[v]) / 2;↵
if (g[v] >= 0 && g[v] <= a[v]) {} // second↵
else access = false;↵
if (sum_g <= g[v]) {} // third↵
else access = false;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while (q--) {↵
int n, m; cin >> n >> m;↵
for (int i = 0; i < n; ++i) cin >> p[i];↵
for (int i = 0; i < n; ++i) cin >> h[i];↵
for (int i = 0; i < n - 1; ++i) {↵
int a, b; cin >> a >> b;↵
--a, --b;↵
gr[a].push_back(b);↵
gr[b].push_back(a);↵
}↵
dfs(0);↵
cout << (access ? "YES" : "NO") << endl;↵
access = true;↵
for (int i = 0; i < n; ++i) gr[i].clear();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388D]↵
↵
Idea: [user:Denisov,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388D]↵
</spoiler>↵
↵
<spoiler summary="Solution (Denisov)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define all(a) a.begin(),a.end()↵
↵
using namespace std;↵
↵
vector <vector <int> > edge;↵
vector <ll> a;↵
vector <int> b, used;↵
vector <int> order[2];↵
ll ans;↵
inline void dfs (int v) {↵
used[v] = 1;↵
for (int to : edge[v]) {↵
if (!used[to]) dfs(to);↵
}↵
ans += a[v];↵
if (b[v] != -1 && a[v] > 0) {↵
a[b[v]] += a[v];↵
}↵
if (a[v] > 0) {↵
order[0].push_back(v);↵
}↵
else {↵
order[1].push_back(v);↵
}↵
}↵
inline void solve () {↵
for (auto &i : edge) i.clear();↵
edge.clear();↵
a.clear();↵
order[0].clear();↵
order[1].clear();↵
b.clear();↵
used.clear();↵
int n, x;↵
cin >> n;↵
edge.resize(n);↵
a.resize(n);↵
b.resize(n);↵
for (auto &i : a) cin >> i;↵
for (int i = 0; i < n; i++) {↵
cin >> x;↵
if (x != -1) {↵
--x;↵
edge[x].push_back(i);↵
}↵
b[i] = x;↵
}↵
ans = 0;↵
used.assign(n, 0);↵
for (int i = 0; i < n; i++) {↵
if (!used[i]) {↵
dfs(i);↵
}↵
}↵
cout << ans << '\n';↵
reverse(all(order[1]));↵
for (auto &i : order[0]) cout << i + 1 << ' ';↵
for (auto &i : order[1]) cout << i + 1 << ' ';↵
cout << '\n';↵
}↵
main()↵
{↵
ios::sync_with_stdio(0);↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
solve();↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
↵
#define Vanya Unstoppable↵
↵
using namespace std;↵
↵
signedint main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
intqn;↵
cin >>qn;↵
↵
while (q--) {↵
int n; cin >> n;↵
intlong long a[n];↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
↵
set < int > s;↵
for (int i = 0; i < n; ++i) {↵
s.insert(i);↵
}↵
↵
int b[n];↵
vector < int > sz(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> b[i]; --b[i];↵
if (b[i] == -2) continue;↵
++sz[b[i]];↵
if (sz[b[i]] == 1) {↵
s.erase(b[i]);↵
}↵
}↵
}↵
intlong long sum = 0;↵
vector < int > ans[2];↵
↵
while (!s.empty()) {↵
int v = *s.begin();↵
s.erase(s.begin());↵
int w = b[v];↵
sum += a[v];↵
if (a[v] >= 0) {↵
if (w >= 0) {↵
a[w] += a[v];↵
}↵
ans[0].push_back(v);↵
} else {↵
ans[1].push_back(v);↵
}↵
if (w >= 0) {↵
--sz[w];↵
if (sz[w] == 0) {↵
s.insert(w);↵
}↵
}↵
}↵
↵
cout << sum << endl;↵
for (int to : ans[0]) cout << to + 1 << ' ';↵
↵
reverse(ans[1].begin(), ans[1].end());↵
↵
for (int to : ans[1]) cout << to + 1 << ' ';↵
cout << endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388E]↵
↵
Idea: [user:perekopskiy,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388E]↵
</spoiler>↵
↵
<spoiler summary="Solution (perekopskiy)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define pb push_back↵
#define x first↵
#define y second↵
↵
using namespace std;↵
↵
const int N = 1e5 + 10;↵
const double eps = 1e-9;↵
↵
double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x;↵
int ind_l, ind_r;↵
↵
double point_pr(double x, double y, double ctg) {↵
return x - y * ctg;↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int n;↵
vector<pair<double, int> > q;↵
vector<pair<double, pair<int, int> > > events, prom_left, prom_right;↵
cin >> n;↵
pair<double, double> mx, mn;↵
mx = {-1.0, -1.0};↵
mn = {2e9, 2e9};↵
mn_x = 2e9;↵
mx_x = -2e9;↵
for(int i = 0; i < n; ++i) {↵
cin >> xl[i] >> xr[i] >> y[i];↵
↵
if(xl[i] < mn_x) {↵
mn_x = xl[i];↵
}↵
if(xr[i] > mx_x) {↵
mx_x = xr[i];↵
}↵
↵
if(mx.y < y[i]) {↵
mx.y = y[i];↵
mx.x = xl[i];↵
ind_l = i;↵
}↵
else if(mx.y == y[i] && mx.x > xl[i]) {↵
mx.y = y[i];↵
mx.x = xl[i];↵
ind_l = i;↵
}↵
↵
if(mn.y > y[i]) {↵
mn.y = y[i];↵
mn.x = xl[i];↵
ind_r = i;↵
}↵
else if(mn.y == y[i] && mn.x < xl[i]) {↵
mn.y = y[i];↵
mn.x = xl[i];↵
ind_r = i;↵
}↵
}↵
double a1, a2;↵
for(int i = 0; i < n; ++i) {↵
for(int j = 0; j < n; ++j) {↵
if(y[i] > y[j]) {↵
a1 = (xr[i] - xl[j]) / (y[i] - y[j]);↵
a2 = (xl[i] - xr[j]) / (y[i] - y[j]);↵
q.pb({a1, 1});↵
q.pb({a2, 2});↵
↵
a1 = (xl[i] - xl[j]) / (y[i] - y[j]);↵
a2 = (xr[i] - xr[j]) / (y[i] - y[j]);↵
events.pb({a1, {i, j}});↵
events.pb({a2, {-i - 1, j}});↵
}↵
}↵
}↵
↵
if(q.empty()) {↵
cout << fixed << setprecision(9) << mx_x - mn_x << endl;↵
return 0;↵
}↵
↵
sort(q.rbegin(), q.rend());↵
int cnt = 0;↵
double last = 0;↵
for(auto i : q) {↵
if(i.y == 2) {↵
--cnt;↵
if(!cnt) {↵
events.pb({i.x, {-1e9, -1e9}});↵
}↵
}↵
else {↵
if(!cnt) {↵
events.pb({i.x, {-1e9, -1e9}});↵
}↵
++cnt;↵
}↵
}↵
sort(events.rbegin(), events.rend());↵
double ans = 1e18, ang;↵
last = -1e18;↵
for(auto i : events) {↵
if(i.y.x == i.y.y) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_left) {↵
s.insert(j.y.x);↵
if(j.y.x == ind_l) {↵
to_check.pb(j.y.y);↵
}↵
}↵
prom_left.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_l = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
↵
for(auto j : prom_right) {↵
s.insert(j.y.y);↵
if(j.y.y == ind_r) {↵
to_check.pb(-j.y.x - 1);↵
}↵
}↵
prom_right.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_r = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
↵
double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x);↵
if(ans > res) {↵
ans = res;↵
ang = i.x;↵
}↵
}↵
else if(i.y.x < 0) {↵
if(abs(i.x - last) > eps) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_right) {↵
s.insert(j.y.y);↵
if(j.y.y == ind_r) {↵
to_check.pb(-j.y.x - 1);↵
}↵
}↵
prom_right.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_r = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
}↵
prom_right.pb(i);↵
}↵
else {↵
if(abs(i.x - last) > eps) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_left) {↵
s.insert(j.y.x);↵
if(j.y.x == ind_l) {↵
to_check.pb(j.y.y);↵
}↵
}↵
prom_left.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_l = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
}↵
prom_left.pb(i);↵
}↵
last = i.x;↵
}↵
cout << fixed << setprecision(9) << ans << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
Idea: [user:Denisov,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388A]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while(q--){↵
int n; cin >> n;↵
if(n <= 30){↵
cout << "NO" << endl;↵
}↵
else{↵
cout << "YES" << endl;↵
if(n == 36 || n == 40 || n == 44){↵
cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl;↵
}↵
else{↵
cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl;↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388B]↵
↵
Idea: [user:Karavaev1101,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388B]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while (q--) {↵
int n; cin >> n;↵
int x = (n + 3) / 4;↵
for (int i = 0; i < n - x; ++i) {↵
cout << 9;↵
}↵
for (int i = 0; i < x; ++i) {↵
cout << 8;↵
}↵
cout << endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388C]↵
↵
Idea: [user:Karavaev1101,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388C]↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 1e5 + 7;↵
↵
vector < int > gr[N];↵
↵
bool access = true;↵
↵
int p[N], h[N], a[N], g[N];↵
↵
void dfs(int v, int ancestor = -1) {↵
a[v] = p[v];↵
int sum_g = 0;↵
for (int to : gr[v]) {↵
if (to == ancestor) continue;↵
dfs(to, v);↵
sum_g += g[to];↵
a[v] += a[to];↵
}↵
if ((a[v] + h[v]) % 2 == 0) {} // first↵
else access = false;↵
g[v] = (a[v] + h[v]) / 2;↵
if (g[v] >= 0 && g[v] <= a[v]) {} // second↵
else access = false;↵
if (sum_g <= g[v]) {} // third↵
else access = false;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int q;↵
cin >> q;↵
↵
while (q--) {↵
int n, m; cin >> n >> m;↵
for (int i = 0; i < n; ++i) cin >> p[i];↵
for (int i = 0; i < n; ++i) cin >> h[i];↵
for (int i = 0; i < n - 1; ++i) {↵
int a, b; cin >> a >> b;↵
--a, --b;↵
gr[a].push_back(b);↵
gr[b].push_back(a);↵
}↵
dfs(0);↵
cout << (access ? "YES" : "NO") << endl;↵
access = true;↵
for (int i = 0; i < n; ++i) gr[i].clear();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388D]↵
↵
Idea: [user:Denisov,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388D]↵
</spoiler>↵
↵
<spoiler summary="Solution (Denisov)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define all(a) a.begin(),a.end()↵
↵
using namespace std;↵
↵
vector <vector <int> > edge;↵
vector <ll> a;↵
vector <int> b, used;↵
vector <int> order[2];↵
ll ans;↵
inline void dfs (int v) {↵
used[v] = 1;↵
for (int to : edge[v]) {↵
if (!used[to]) dfs(to);↵
}↵
ans += a[v];↵
if (b[v] != -1 && a[v] > 0) {↵
a[b[v]] += a[v];↵
}↵
if (a[v] > 0) {↵
order[0].push_back(v);↵
}↵
else {↵
order[1].push_back(v);↵
}↵
}↵
inline void solve () {↵
for (auto &i : edge) i.clear();↵
edge.clear();↵
a.clear();↵
order[0].clear();↵
order[1].clear();↵
b.clear();↵
used.clear();↵
int n, x;↵
cin >> n;↵
edge.resize(n);↵
a.resize(n);↵
b.resize(n);↵
for (auto &i : a) cin >> i;↵
for (int i = 0; i < n; i++) {↵
cin >> x;↵
if (x != -1) {↵
--x;↵
edge[x].push_back(i);↵
}↵
b[i] = x;↵
}↵
ans = 0;↵
used.assign(n, 0);↵
for (int i = 0; i < n; i++) {↵
if (!used[i]) {↵
dfs(i);↵
}↵
}↵
cout << ans << '\n';↵
reverse(all(order[1]));↵
for (auto &i : order[0]) cout << i + 1 << ' ';↵
for (auto &i : order[1]) cout << i + 1 << ' ';↵
cout << '\n';↵
}↵
main()↵
{↵
ios::sync_with_stdio(0);↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
solve();↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Karavaev1101)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
↵
↵
using namespace std;↵
↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int
cin >>
↵
int n; cin >> n;↵
int
↵
set < int > s;↵
↵
int b[n];↵
}↵
↵
while (!s.empty()) {↵
↵
cout << sum << endl;↵
↵
reverse(ans[1].begin(), ans[1].end());↵
↵
for (int to : ans[1]) cout << to + 1 << ' ';↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1388E]↵
↵
Idea: [user:perekopskiy,2020-07-30]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1388E]↵
</spoiler>↵
↵
<spoiler summary="Solution (perekopskiy)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define pb push_back↵
#define x first↵
#define y second↵
↵
using namespace std;↵
↵
const int N = 1e5 + 10;↵
const double eps = 1e-9;↵
↵
double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x;↵
int ind_l, ind_r;↵
↵
double point_pr(double x, double y, double ctg) {↵
return x - y * ctg;↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int n;↵
vector<pair<double, int> > q;↵
vector<pair<double, pair<int, int> > > events, prom_left, prom_right;↵
cin >> n;↵
pair<double, double> mx, mn;↵
mx = {-1.0, -1.0};↵
mn = {2e9, 2e9};↵
mn_x = 2e9;↵
mx_x = -2e9;↵
for(int i = 0; i < n; ++i) {↵
cin >> xl[i] >> xr[i] >> y[i];↵
↵
if(xl[i] < mn_x) {↵
mn_x = xl[i];↵
}↵
if(xr[i] > mx_x) {↵
mx_x = xr[i];↵
}↵
↵
if(mx.y < y[i]) {↵
mx.y = y[i];↵
mx.x = xl[i];↵
ind_l = i;↵
}↵
else if(mx.y == y[i] && mx.x > xl[i]) {↵
mx.y = y[i];↵
mx.x = xl[i];↵
ind_l = i;↵
}↵
↵
if(mn.y > y[i]) {↵
mn.y = y[i];↵
mn.x = xl[i];↵
ind_r = i;↵
}↵
else if(mn.y == y[i] && mn.x < xl[i]) {↵
mn.y = y[i];↵
mn.x = xl[i];↵
ind_r = i;↵
}↵
}↵
double a1, a2;↵
for(int i = 0; i < n; ++i) {↵
for(int j = 0; j < n; ++j) {↵
if(y[i] > y[j]) {↵
a1 = (xr[i] - xl[j]) / (y[i] - y[j]);↵
a2 = (xl[i] - xr[j]) / (y[i] - y[j]);↵
q.pb({a1, 1});↵
q.pb({a2, 2});↵
↵
a1 = (xl[i] - xl[j]) / (y[i] - y[j]);↵
a2 = (xr[i] - xr[j]) / (y[i] - y[j]);↵
events.pb({a1, {i, j}});↵
events.pb({a2, {-i - 1, j}});↵
}↵
}↵
}↵
↵
if(q.empty()) {↵
cout << fixed << setprecision(9) << mx_x - mn_x << endl;↵
return 0;↵
}↵
↵
sort(q.rbegin(), q.rend());↵
int cnt = 0;↵
double last = 0;↵
for(auto i : q) {↵
if(i.y == 2) {↵
--cnt;↵
if(!cnt) {↵
events.pb({i.x, {-1e9, -1e9}});↵
}↵
}↵
else {↵
if(!cnt) {↵
events.pb({i.x, {-1e9, -1e9}});↵
}↵
++cnt;↵
}↵
}↵
sort(events.rbegin(), events.rend());↵
double ans = 1e18, ang;↵
last = -1e18;↵
for(auto i : events) {↵
if(i.y.x == i.y.y) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_left) {↵
s.insert(j.y.x);↵
if(j.y.x == ind_l) {↵
to_check.pb(j.y.y);↵
}↵
}↵
prom_left.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_l = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
↵
for(auto j : prom_right) {↵
s.insert(j.y.y);↵
if(j.y.y == ind_r) {↵
to_check.pb(-j.y.x - 1);↵
}↵
}↵
prom_right.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_r = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
↵
double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x);↵
if(ans > res) {↵
ans = res;↵
ang = i.x;↵
}↵
}↵
else if(i.y.x < 0) {↵
if(abs(i.x - last) > eps) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_right) {↵
s.insert(j.y.y);↵
if(j.y.y == ind_r) {↵
to_check.pb(-j.y.x - 1);↵
}↵
}↵
prom_right.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_r = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
}↵
prom_right.pb(i);↵
}↵
else {↵
if(abs(i.x - last) > eps) {↵
unordered_set<int> s;↵
vector<int> to_check;↵
for(auto j : prom_left) {↵
s.insert(j.y.x);↵
if(j.y.x == ind_l) {↵
to_check.pb(j.y.y);↵
}↵
}↵
prom_left.clear();↵
for(auto j : to_check) {↵
if(!s.count(j)) {↵
ind_l = j;↵
break;↵
}↵
}↵
s.clear();↵
to_check.clear();↵
}↵
prom_left.pb(i);↵
}↵
last = i.x;↵
}↵
cout << fixed << setprecision(9) << ans << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
