Cow-libi

Explicación

Pensemos primero cómo determinar si una vaca puede ir de $(x_1, y_1)$ en el tiempo $t_1$ a $(x_2, y_2)$ en el tiempo $t_2$ .

El camino más corto que puede tomar una vaca es la recta que une $(x_1, y_1)$ con $(x_2, y_2)$ , que tiene longitud

\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

por la fórmula de la distancia.

Ahora, el viaje de la vaca es posible si y solo si esta longitud no es mayor que $t_2 - t_1$ . En otras palabras, tenemos la siguiente desigualdad:

(t_2 - t_1)^2 \geq (x_2 - x_1)^2 + (y_2 - y_1)^2

Por tanto, podemos comprobar si la desigualdad se cumple para cada vaca y cada sitio de pastoreo, y si cada sitio de pastoreo satisface la desigualdad para una vaca particular, entonces es sospechosa. En caso contrario, debe ser inocente.

Ahora, en lugar de usar fuerza bruta para recorrer todas las vacas y sitios de pastoreo, usamos la condición de que una vaca puede alcanzar cualquier sitio de pastoreo desde otro dentro de los tiempos especificados.

Consideremos una vaca en $(x_1, y_1)$ en el tiempo $t_1$ y dos sitios de pastoreo en $(x_2, y_2)$ y $(x_3, y_3)$ en los tiempos $t_2$ y $t_3$ , donde $t_1 < t_2 < t_3$ . Si la vaca puede alcanzar el sitio de pastoreo en $(x_2, y_2)$ , entonces también puede alcanzar el de $(x_3, y_3)$ . Lo mismo vale cuando $t_1 > t_2 > t_3$ .

Esto significa que, para cada vaca, solo necesitamos comprobar los dos sitios de pastoreo con tiempos más cercanos a su tiempo reportado. Podemos hallar estos dos sitios ordenando la lista de sitios de pastoreo por tiempo y usando búsqueda binaria, que es lo bastante rápido para resolver el problema.

Implementación

Complejidad temporal: $\mathcal{O}((N+G)\log G)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
struct Event {
	int t, x, y;
 
	bool operator<(const Event &other) const { return t < other.t; }
};
 
Event read() {
	int x, y, t;
	cin >> x >> y >> t;
	return {t, x, y};
}
 
bool reachable(const Event &a, const Event &b) {
	long long dx = a.x - b.x;
	long long dy = a.y - b.y;
	long long dt = a.t - b.t;
	return dx * dx + dy * dy <= dt * dt;
}
 
int main() {
	int g, n;
	cin >> g >> n;
 
	vector<Event> grazings(g);
	for (int i = 0; i < g; i++) { grazings[i] = read(); }
 
	sort(grazings.begin(), grazings.end());
 
	int ans = 0;
	for (int i = 0; i < n; i++) {
		Event alibi = read();
		int pos =
		    upper_bound(grazings.begin(), grazings.end(), alibi) - grazings.begin();
 
		bool innocent = false;
		for (int y = pos - 1; y <= pos; y++) {
			if (0 <= y && y < g) { innocent |= !reachable(grazings[y], alibi); }
		}
 
		ans += innocent;
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class CowLibi {
	private static class Event implements Comparable<Event> {
		int t, x, y;
 
		private Event(int t, int x, int y) {
			this.t = t;
			this.x = x;
			this.y = y;
		}
 
		@Override
		public int compareTo(Event other) {
			return Integer.compare(this.t, other.t);
		}
	}
 
	private static Event read(BufferedReader br) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		return new Event(t, x, y);
	}
 
	private static boolean reachable(Event a, Event b) {
		long dx = a.x - b.x;
		long dy = a.y - b.y;
		long dt = a.t - b.t;
		return dx * dx + dy * dy <= dt * dt;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int g = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
 
		List<Event> grazings = new ArrayList<>();
		for (int i = 0; i < g; i++) { grazings.add(read(br)); }
 
		Collections.sort(grazings);
 
		int ans = 0;
		for (int i = 0; i < n; i++) {
			Event alibi = read(br);
 
			int pos = Collections.binarySearch(grazings, alibi);
			if (pos < 0) { pos = -pos - 1; }
 
			boolean innocent = false;
			for (int y = pos - 1; y <= pos; y++) {
				if (0 <= y && y < g) { innocent |= !reachable(grazings.get(y), alibi); }
			}
 
			ans += innocent ? 1 : 0;
		}
 
		System.out.println(ans);
	}
}


import bisect
from typing import Tuple
 
g, n = map(int, input().split())
 
 
def read():
	x, y, t = map(int, input().split())
	return t, x, y
 
 
def reachable(a: Tuple[int, int, int], b: Tuple[int, int, int]) -> bool:
	dx = a[1] - b[1]
	dy = a[2] - b[2]
	dt = a[0] - b[0]
	return dx * dx + dy * dy <= dt * dt
 
 
grazings = sorted(read() for _ in range(g))
 
ans = 0
for _ in range(n):
	alibi = read()
	pos = bisect.bisect(grazings, alibi)
 
	innocent = False
	for y in range(pos - 1, pos + 1):
		if 0 <= y < g:
			innocent |= not reachable(grazings[y], alibi)
 
	ans += innocent
 
print(ans)