## Algorithm

Problem Name: Data Structures - Taxicab Driver's Problem

In this HackerRank in Data Structures - Taxicab Driver's Problem solutions,

Burger Town is a city that consists of N special junctions and N - 1 pathways. There is exactly one shortest path between each pair of junctions. Junction i is located at (xi,yi) and the distance between two junctions i,j is defined by the Taxicab geometry.

Tim has recently afforded a taxicab to work as a taxicab driver. His vehicle was very cheap, but has a very big flaw. It can only drive H units horizontally and V units vertically before refueling.

If a customer wants to be brought from a junction i to another junction j then this car is only capable of driving the route, iff the sum of horizontal distances and the sum of vertical distances on this path are less than or equal to H and V respectively.

Also, there is a unique path between any two junctions.

Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs (i,j) such that it is not possible to drive a customer from junction i to junction j.

Input Format

On the first line you will be given N,H and V separated by a single space.
Each of the next N lines contains two space separated integers xi,yi denoting the location of junction i. Each of the next N - 1 lines contains two space separated integers describing a path existing between ui,vi , i.e., there is a path between ui and vi.

Output Format

Output the number of unordered pairs (i,j) such that it is not possible to drive from i to j.

Constraints

2 <= N <= 10**5

0 <= H,V <= 10**14

0 <= xi, yi <= 10**9

Sample Input

``````3 2 1
0 0
1 1
2 0
1 2
2 3
``````

Sample Output

``````1
``````

Explanation

The car is only capable of driving H = 2 units horizontally and V = 1 unit vertically. The horizontal distance between junction 1 and 3(via 2) is equal to 2(0 -> 1 -> 2), which fits under the horizontal limit of the car. The vertical distance between 1 and 3 is also equal to 2(0 -> 1 -> 2), but this is not possible for this car since 2 > V

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define have(self, id) ((self)[(id) >> 5] &  (1U << ((id) & 31U)))
#define inv(self, id)  ((self)[(id) >> 5] ^= (1U << ((id) & 31U)))

static inline unsigned delta(unsigned self, unsigned other) {
return (self  <  other) ? (other - self) : (self - other);
}

void ascending_stbl(unsigned length, unsigned long *weights, unsigned *self) {
unsigned
at, span,
at_left, at_right,
*left, *right,
order[length];

for (span = 1; span  <  length; span <<= 1)
for (left = &((unsigned *)memcpy(order, self, sizeof(order[0]) * length))[at = length]; at > span; ) {
right = left - (at_right = span);
at_left = (at  <  (span << 1)) ? (at - span) : span;

for (left -= at_left + at_right; at_left && at_right;
self[--at] = (weights[left[at_left - 1]] > weights[right[at_right - 1]])
? left[--at_left] : right[--at_right]);

memcpy(&self[at -= (at_left | at_right)], right, at_right * sizeof(self[0]));
}
}

int main() {
unsigned vertex_cnt;
unsigned long limits[2];
scanf("%u %lu %lu", &vertex_cnt, &limits[0], &limits[1]);

unsigned
cords[2][vertex_cnt],
neighbors[vertex_cnt << 1],
ancestors[vertex_cnt],
indices[vertex_cnt + 2],
next, tail, others, at;

for (at = 0; at  <  vertex_cnt; at++)
scanf("%u %u", &cords[0][at], &cords[1][at]);

for (at >>= 1; at--; ((unsigned long *)ancestors)[at] = 0x100000001UL * vertex_cnt);
for (ancestors[at += vertex_cnt] = vertex_cnt; at--; ancestors[others] = tail)
if (ancestors[(scanf("%u %u", &tail, &others), --tail, --others)] != vertex_cnt)
for (tail ^= others, others ^= tail, tail ^= others;
ancestors[others] != vertex_cnt;
others = next
) {
next = ancestors[others];
ancestors[others] = tail;
tail = others;
}

memset(indices, 0, sizeof(indices));
for (at = vertex_cnt; at--; *(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);
for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);
for (at = vertex_cnt; at--; neighbors[--indices[ancestors[at]]] = at);

unsigned
history[vertex_cnt],
weights[vertex_cnt + 1];

at += vertex_cnt;
history[at] = neighbors[at];
for (others = 0; others  <  at; others++) {
history[others] = history[at];
at -= (indices[history[at] + 1] - indices[history[at]]) - 1U;
memcpy(
&history[at],
&neighbors[indices[history[others]]],
sizeof(history[0]) * (indices[history[others] + 1] - indices[history[others]])
);
}
for (at = vertex_cnt >> 1; at--; ((unsigned long *)weights)[at] = 0x100000001UL);
for (*(unsigned long *)&weights[(at = vertex_cnt) - 1] = 1UL; --at;
weights[ancestors[history[at]]] += weights[history[at]]);

unsigned
offsets[vertex_cnt + 2],
forward[vertex_cnt];
{
unsigned
mass[vertex_cnt],
centroids[vertex_cnt];

centroids[history[0]] = (mass[0] = vertex_cnt);
for (at = 1; at--; weights[next] = 0) {
for (others = (tail = history[at]); (weights[others] << 1)  <  mass[at]; others = ancestors[tail = others]);
for (others = indices[next = others]; others  <  indices[next + 1]; others++)
if ((weights[neighbors[others]] << 1) > mass[at] && neighbors[others] != tail)
others = indices[next = neighbors[others]] - 1;

for (centroids[next] = centroids[history[at]]; others-- > indices[next]; )
if (weights[neighbors[others]]) {
centroids[history[at] = neighbors[others]] = next;
mass[at++] = weights[neighbors[others]];
}

for (others = next; weights[ancestors[others]]; weights[others = ancestors[others]] -= weights[next]);
if (others != next) {
centroids[history[at] = ancestors[next]] = next;
mass[at++] = weights[others];
}
}
memset(offsets, 0, sizeof(offsets));
for (at = vertex_cnt; at--; *(unsigned long *)&offsets[centroids[at]] += 0x100000001UL);
for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)offsets)[at + 1] += ((unsigned long *)offsets)[at]);
for (at = vertex_cnt; at--; forward[--offsets[centroids[at]]] = at);
}

for (at = forward[(tail = vertex_cnt) - 1]; at != vertex_cnt; at = next) {
next = ancestors[at];
ancestors[at] = tail;
tail = at;
}

for (at >>= 1; at--; ((unsigned long *)indices)[at] = 0x200000002UL);
*(unsigned long *)indices = 0x200000001UL;
for (*(unsigned long *)&indices[(at = vertex_cnt) - 1] = 0x100000002UL; at--;
*(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);
for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);
for (at = vertex_cnt; at--; neighbors[--indices[ancestors[at]]] = at);
for (; ++at  <  vertex_cnt; neighbors[--indices[at]] = ancestors[at]);
indices[at + 1] = at << 1;

unsigned
ordered[vertex_cnt << 1],
ranks[vertex_cnt << 1],
sums[vertex_cnt << 1],
deltas[2][vertex_cnt],
seen[((vertex_cnt + 1) >> 5) + 1];

unsigned long
total = 0,
max[2],
(*dists)[2][vertex_cnt << 1] = malloc(sizeof(dists[0]));

memset(seen, 0, sizeof(seen));
inv(seen, at);
for (history[0] = forward[at - 1], at = 1; at--; ) {
inv(seen, history[at]);
dists[0][0][vertex_cnt + history[at]] = (dists[0][1][vertex_cnt + history[at]] = (max[0] = (max[1] = 0UL)));
for (history[tail = vertex_cnt - 1] = history[next = at]; tail  <  vertex_cnt; next++)
for (others = indices[(history[next] = history[tail++]) + 1]; others-- > indices[history[next]]; )
if (have(seen, neighbors[others]) == 0) {
inv(seen, neighbors[others]);
weights[history[--tail] = neighbors[others]] = 1;
ordered[history[tail]] = history[next];

dists[0][0][vertex_cnt + history[tail]] = dists[0][0][vertex_cnt + history[next]]
+ delta(cords[0][history[next]], cords[0][history[tail]]);
dists[0][1][vertex_cnt + history[tail]] = dists[0][1][vertex_cnt + history[next]]
+ delta(cords[1][history[next]], cords[1][history[tail]]);

if (max[0]  <  dists[0][0][vertex_cnt + history[tail]])
max[0] = dists[0][0][vertex_cnt + history[tail]];
if (max[1] < dists[0][1][vertex_cnt + history[tail]])
max[1] = dists[0][1][vertex_cnt + history[tail]];
}
if ((max[0] << 1)  < = limits[0] && (max[1] << 1)  < = limits[1])
continue ;

for (weights[history[at]] = 1; --next > at; inv(seen, history[next]))
weights[ordered[history[next]]] += weights[history[next]];

ranks[history[next++]] = 0;
for (tail = 1, others = next; others  <  (at + weights[history[at]]); )
for (next += weights[history[next]], max[0] = tail; others  <  next; )
if (dists[0][0][vertex_cnt + history[others]] > limits[0]
|| dists[0][1][vertex_cnt + history[others]] > limits[1]) {
total += (max[0] + ((at + weights[history[at]]) - next)) * weights[history[others]];
others += weights[history[others]];
} else {
ancestors[ranks[history[others]] = tail] = ranks[ordered[history[others]]];
dists[0][0][tail] = dists[0][0][vertex_cnt + history[others]];
dists[0][1][tail++] = dists[0][1][vertex_cnt + history[others++]];
}

for (others = tail >> 1; others--; ((unsigned long *)weights)[others] = 0x100000001UL);
for (weights[(others = tail) - 1] = 1; --others; weights[ancestors[others]] += weights[others]) {
dists[0][0][tail + others] = limits[0] - dists[0][0][others];
dists[0][1][tail + others] = limits[1] - dists[0][1][others];

ordered[others - 1] = others;
ordered[tail + others - 2] = tail + others;
}

others = (tail - 1) << 1;
for (ascending_stbl(others, dists[0][1], ordered); others--; ranks[ordered[others]] = others);
for (; ++others  <  (tail - 1); ordered[others] = others + 1)
ordered[tail + others - 1] = tail + others + 1;

ascending_stbl((others <<= 1), dists[0][0], ordered);
memset(sums, 0, others * sizeof(sums[0]));
for (tail = 0; tail  <  others; tail++)
if (ordered[tail] > weights[0]) {
deltas[0][ordered[tail] -= weights[0]] = 0;
for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
deltas[0][ordered[tail]] += sums[next];
ordered[tail] += weights[0];
} else
for (next = ranks[ordered[tail]]; next  <  others; next |= next + 1)
sums[next]++;

unsigned long sum = 0;
deltas[0][0] = weights[0] - 1;
for (others = 1; others  <  weights[0]; ) {
for (tail = weights[others]; tail--; ordered[tail] = others + tail)
ordered[weights[others] + tail] = weights[0] + others + tail;

tail = (weights[others] << 1);
for (ascending_stbl(tail, dists[0][1], ordered); tail--; ranks[ordered[tail]] = tail);

for (tail = weights[others]; tail--; ordered[tail] = others + tail)
ordered[weights[others] + tail] = weights[0] + others + tail;
ascending_stbl(weights[others] << 1, dists[0][0], ordered);

memset(sums, 0, (weights[others] << 1) * sizeof(sums[0]));
for (tail = 0; tail  <  (weights[others] << 1); tail++)
if (ordered[tail] > weights[0]) {
deltas[1][ordered[tail] -= weights[0]] = 0;
for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
deltas[1][ordered[tail]] += sums[next];
ordered[tail] += weights[0];
} else
for (next = ranks[ordered[tail]]; next  <  (weights[others] << 1); next |= next + 1)
sums[next]++;

deltas[1][0] = weights[others];
for (tail = others + (tail >> 1); others  <  tail; others++)
sum += weights[others] * (unsigned long)(
(deltas[0][ancestors[others]] - deltas[0][others])
- (deltas[1][ancestors[others]] - deltas[1][others])
);
}
total += sum >> 1;

others = offsets[history[at] + 1] - offsets[history[at]];
memcpy(&history[at], &forward[offsets[history[at]]], others * sizeof(history[0]));
at += others;
}
printf("%lu", total);

free(dists);
return 0;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

#define FO(i,a,b) for (int i = (a); i  <  (b); i++)
#define sz(v) int(v.size())

using namespace std;

typedef long long ll;

typedef pair < ll,ll> E;
#define dx first
#define dy second
struct edge {
int o;
ll dx, dy;

edge(int o=0, ll dx=0, ll dy=0) : o(o), dx(dx), dy(dy) {}
};

vector < edge> u[100005];
int n; ll DX, DY;
ll Y[100005], X[100005];
int sc[100005];

void delete_from(int x, int y) {
FO(i,0,sz(u[x])) if (u[x][i].o == y) {
swap(u[x][i],u[x].back());
u[x].pop_back();
return;
}
}

void delete_node(int x) {
FO(i,0,sz(u[x])) {
delete_from(u[x][i].o,x);
}
}

void resetsc(int x, int p) {
sc[x] = 1;
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
resetsc(u[x][i].o,x);
sc[x] += sc[u[x][i].o];
}
}

int find_centre(int x, int p, int tsz) {
int lsz = tsz-sc[x];
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
lsz = max(lsz, sc[u[x][i].o]);
int y = find_centre(u[x][i].o,x,tsz);
if (y != -1) return y;
}
if (2*lsz  < = tsz+5) return x;
return -1;
}

void getl(int x, int p, vector < E> &v, ll dx, ll dy) {
if (dx != 0 || dy != 0) v.push_back(E(dx,dy));
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
getl(u[x][i].o, x, v, dx+u[x][i].dx, dy+u[x][i].dy);
}
}

bool cmp(E a, E b) {
if (a.dx != b.dx) return a.dx  <  b.dx;
else return a.dy < b.dy;
}

ll res;
vector < ll> bit;

void ub(int y, int dv) {
for (;y < sz(bit);y+=y&-y) bit[y] += dv;
}

ll qb(int y) {
ll r = 0;
for (;y>0;y-=y&-y) r += bit[y];
return r;
}

ll doitbf(vector < E> p) {
ll RES = 0;
FO(i,0,sz(p)) FO(j,0,i) if (p[i].dx+p[j].dx <= DX && p[i].dy+p[j].dy <= DY) RES++;
return RES;
}

ll doit(vector < E> p) {
//printf("DOIT\n");
//FO(i,0,sz(p)) printf("%lld,%lld\n", p[i].dx, p[i].dy);
ll RES = 0;
vector < E> q;
vector<ll> y;
FO(i,0,sz(p)) {
if (p[i].dx+p[i].dx  < = DX && p[i].dy+p[i].dy <= DY) RES--;
ll qdx = DX-p[i].dx;
ll qdy = DY-p[i].dy;
if (qdx >= 0 && qdy >= 0) q.push_back(E(qdx, qdy));
}
FO(i,0,sz(p)) y.push_back(p[i].dy);
FO(i,0,sz(q)) y.push_back(q[i].dy);
sort(y.begin(),y.end());
y.resize(unique(y.begin(),y.end())-y.begin());
bit.resize(sz(y)+5);
FO(i,0,sz(bit)) bit[i] = 0;

sort(p.begin(),p.end(),cmp);
sort(q.begin(),q.end(),cmp);

int pi = 0, qi = 0;
while (qi  <  sz(q)) {
if (pi < sz(p) && !cmp(q[qi],p[pi])) {
int yv = lower_bound(y.begin(),y.end(),p[pi].dy)-y.begin()+1;
ub(yv,1);
pi++;
} else {
int yv = lower_bound(y.begin(),y.end(),q[qi].dy)-y.begin()+1;
RES += qb(yv);
qi++;
}
}
RES /= 2;

return RES;
}

void testdoit() {
vector < E> v;
DX = DY = 100;
FO(i,0,1000) v.push_back(E(rand()%DX,rand()%DY));
printf("%lld %lld\n", doit(v), doitbf(v));
}

void solve(int x) {
if (sz(u[x]) == 0) return;
resetsc(x,-1);
x = find_centre(x,-1,sc[x]);
vector < E> cv;
cv.push_back(E(0,0));
FO(i,0,sz(u[x])) {
vector < E> v;
getl(u[x][i].o,x,v,u[x][i].dx,u[x][i].dy);
res -= doit(v);
FO(j,0,sz(v)) cv.push_back(v[j]);
}
res += doit(cv);
delete_node(x);
FO(i,0,sz(u[x])) solve(u[x][i].o);
}

int main() {
//testdoit();
//return 0;

scanf("%d %lld %lld", &n, &DX, &DY);
FO(i,0,n) {
scanf("%lld %lld", &X[i], &Y[i]);
}
FO(i,0,n-1) {
int a,b; scanf("%d %d", &a, &b); a--; b--;
u[a].push_back(edge(b,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
u[b].push_back(edge(a,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
}
solve(0);
ll T = (n * 1ll * (n-1)) / 2;
printf("%lld\n", T - res);
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

static class Pair implements Comparable < Pair> {
long fi;
long se;

public Pair(long fi, long se) {
this.fi = fi;
this.se = se;
}

@Override
public int compareTo(Pair o) {
if (fi != o.fi) {
return fi > o.fi ? 1 : -1;
}
if (se == o.se) {
return 0;
}
return se > o.se ? 1 : -1;
}
}

static boolean[] cut;
static int[] size;

static int getSize(int v, int p) {
size[v] = 1;
for (int u: e[v]) {
if (u != p && ! cut[u]) {
size[v] += getSize(u, v);
}
}
return size[v];
}

static Pair[] a;
static List < Integer>[] e;
static Pair[] b;

static int getDist(int v, int p, int i, long hh, long vv) {
hh += Math.abs(a[v].fi - a[p].fi);
vv += Math.abs(a[v].se - a[p].se);
b[i++] = new Pair(hh, vv);
for (int u: e[v]) {
if (u != p && ! cut[u]) {
i = getDist(u, v, i, hh, vv);
}
}
return i;
}

static public int lowerBound(long[] arr, int len, long key) {
if (key  < = arr[0]) {
return 0;
}
if (key > arr[len - 1]) {
return 0;
}

int index = Arrays.binarySearch(arr, 0, len, key);
if (index  <  0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
while (index > 0 && arr[index-1] == key) {
index--;
}
return index;
}

static int upperBound(long[] arr, int len, long key) {
int index = Arrays.binarySearch(arr, 0, len, key);
if (index  <  0) {
index = - index - 1;
if (index < 0) {
return 0;
}
if (index >= len) {
return len;
}
}
while (index  <  len && arr[index] == key) {
index++;
}
return index;
}

static int[] fenwick;
static long[] c;
static long h;
static long v;

static long calc(int l, int r) {
int n = r-l;
long ret = 0;
Arrays.sort(b, l, r);
for (int i = l; i  <  r; i++) {
c[i-l] = b[i].se;
}
Arrays.sort(c, 0, n);
Arrays.fill(fenwick, 0, n, 0);
for (int j = l, i = r; --i >= l; ) {
for (; j  <  r && b[j].fi+b[i].fi <= h; j++)
for (int x = lowerBound(c, n, b[j].se); x  <  n; x |= x+1) {
fenwick[x]++;
}
for (int x = upperBound(c, n, v-b[i].se); x > 0; x &= x-1) {
ret += fenwick[x-1];
}
}
return ret;
}

static Object[] divide(int l, int v) {
getSize(v, -1);
int nn = size[v];
int p = -1;
for(;;) {
int ch = -1;
for (int u: e[v]) {
if (u != p && ! cut[u] && 2*size[u] >= nn) {
ch = u;
break;
}
}
if (ch  <  0) {
break;
}
p = v;
v = ch;
}
cut[v] = true;
b[l] = new Pair(0, 0);
int i = l+1;
long ret = 0;
for (int u: e[v]) {
if (! cut[u]) {
Object[] r = divide(i, u);
ret += (long)r[1];
getDist(u, v, i, 0, 0);
ret -= calc(i, (int)r[0]);
i = (int)r[0];
}
}
cut[v] = false;
ret += calc(l, i) - 1;
return new Object[]{i, ret};
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
h = Long.parseLong(st.nextToken());
v = Long.parseLong(st.nextToken());

a = new Pair[n];
e = new List[n];
for (int i = 0; i  <  n; i++) {
long fi = Long.parseLong(st.nextToken());
long se = Long.parseLong(st.nextToken());

a[i] = new Pair(fi, se);
e[i] = new LinkedList < >();
}

for (int i = 0; i  <  n - 1; i++) {
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;

}

cut = new boolean[n];
size = new int[n];
b = new Pair[n];
fenwick = new int[n];
c = new long[n];
long result = (long)(n-1)*n - ((long)divide(0, 0)[1]) >> 1;
bw.write(String.valueOf(result));
bw.newLine();
bw.close();
br.close();
}
}
``````
Copy The Code &

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
from collections import namedtuple
import bisect
import sys

DistTuple = namedtuple('distance', ['h', 'v'])

def insort_right(arr, dist, hv):
x_key = dist.h if hv == 'h' else dist.v
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
a_mid = arr[mid].h if hv == 'h' else arr[mid].v
if x_key < a_mid:
hi = mid
else:
lo = mid + 1
arr.insert(lo, dist)

def bisect_right(arr, x_key, hv):
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
a_mid = arr[mid].h if hv == 'h' else arr[mid].v
if x_key < a_mid:
hi = mid
else:
lo = mid + 1
return lo

class DistsGroup:
def __init__(self):
self.delta_h = 0
self.delta_v = 0
dist = DistTuple(0, 0)
self.dists_h_sorted = [dist]
self.dists_v_sorted = [dist]

def append_dist(self, h, v, append=True):
self.delta_h += h
self.delta_v += v
dist = DistTuple(-self.delta_h, -self.delta_v)
if append:
insort_right(self.dists_h_sorted, dist, 'h')
insort_right(self.dists_v_sorted, dist, 'v')
index_h = bisect_right(self.dists_h_sorted, H_max - self.delta_h, 'h')
for elem in self.dists_h_sorted[index_h:]:
self.dists_v_sorted.remove(elem)
del (self.dists_h_sorted[index_h:])
index_v = bisect_right(self.dists_v_sorted, V_max - self.delta_v, 'v')
for elem in self.dists_v_sorted[index_v:]:
self.dists_h_sorted.remove(elem)
del (self.dists_v_sorted[index_v:])
if append:
paths_count = max(0, len(self.dists_v_sorted) - 1)
return paths_count

def append_group(self, other_group, h, v):
good_cross_paths = 0
other_group.append_dist(h, v, False)
dists_h1 = self.dists_h_sorted
delta_h1 = self.delta_h
delta_v1 = self.delta_v
dists_h2 = other_group.dists_h_sorted
delta_h2 = other_group.delta_h
delta_v2 = other_group.delta_v
dists_only_v2 = []
dist_h2_index = 0
dist_h2_len = len(dists_h2)
if len(dists_h1) and len(dists_h2) and dists_h1[-1].h + delta_h1 + dists_h2[-1].h + delta_h2 < H_max and self.dists_v_sorted[-1].v + delta_v1 + other_group.dists_v_sorted[-1].v + delta_v2 < V_max:
good_cross_paths += len(dists_h1) * len(dists_h2)
else:
for dist_h1 in reversed(dists_h1):
rest_h = H_max - (dist_h1.h + delta_h1)
rest_v = V_max - (dist_h1.v + delta_v1)
while dist_h2_index < dist_h2_len:
if dists_h2[dist_h2_index].h + delta_h2 <= rest_h:
bisect.insort_right(dists_only_v2, dists_h2[dist_h2_index].v + delta_v2)
dist_h2_index += 1
else:
break
dist_v2_index = bisect.bisect_right(dists_only_v2, rest_v)
good_cross_paths += dist_v2_index
for dist_h2 in dists_h2:
dist_new = DistTuple((dist_h2.h + delta_h2) - delta_h1, (dist_h2.v + delta_v2) - delta_v1)
self.dists_h_sorted.append(dist_new)
self.dists_v_sorted.append(dist_new)
self.dists_h_sorted.sort()
self.dists_v_sorted.sort(key=lambda k: k.v)
return good_cross_paths

good_paths = 0

N, H_max, V_max = map(int, sys.stdin.readline().split())
junctions = {}
for i in range(1, N + 1):
junctions[i] = {'x': xi, 'y': yi, 'edges': [], 'dists_group': None}
for i in range(1, N):
dH = abs(junctions[ui]['x'] - junctions[vi]['x'])
dV = abs(junctions[ui]['y'] - junctions[vi]['y'])
junctions[ui]['edges'].append({'junction_id': vi, 'dH': dH, 'dV': dV})
junctions[vi]['edges'].append({'junction_id': ui, 'dH': dH, 'dV': dV})
one_edge_queue = []
for key, value in junctions.items():
edge_count = len(junctions[key]['edges'])
junctions[key]['edge_count'] = edge_count
if edge_count == 1:
one_edge_queue.append(key)
junctions[key]['dists_group'] = DistsGroup()
while len(one_edge_queue) > 1:
junction_id = one_edge_queue[0]
edge_to_next = junctions[junction_id]['edges'][0]
next_junction_id = edge_to_next['junction_id']
if junctions[next_junction_id]['dists_group']:
else:
dists_group = junctions[junction_id]['dists_group']
junctions[next_junction_id]['dists_group'] = dists_group
for edge in junctions[next_junction_id]['edges']:
if edge['junction_id'] == junction_id:
junctions[next_junction_id]['edges'].remove(edge)
break
if len(junctions[next_junction_id]['edges']) == 1:
one_edge_queue.append(next_junction_id)
one_edge_queue.remove(junction_id)
print(int(N * (N - 1) / 2) - good_paths)

``````
Copy The Code &