Skip to Content
CTRL K

The Troublesome Frog

Explicación

Como N≤5000N \le 5000, podemos iterar sobre cada par de puntos.

Para evitar procesar el mismo conjunto de puntos varias veces, solo buscamos los pares que no tienen un punto colineal a igual distancia a la izquierda. Una vez que esta comprobación tiene éxito, vemos cuántos puntos igualmente espaciados hay a la derecha.

Implementación

Complejidad temporal: O(Nlog⁡N+N2⋅max⁡(R,C))\mathcal{O}(N \log N + N^2 \cdot \max(R, C))

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
// BeginCodeSnip{Point Struct}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
	Point operator-(const Point &other) { return {x - other.x, y - other.y}; }
	Point operator+(const Point &other) { return {x + other.x, y + other.y}; }
	bool operator<(const Point &other) const {
		return x < other.x || (x == other.x && y < other.y);
	}
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
int main() {
	int r, c, n;
	cin >> r >> c >> n;
	vector<Point> points(n);
 
	// Hashing a struct is too complicated, so let's use a boolean array
	array<bool, 100000000> seen;
	auto hash = [&](const Point &p) -> int { return p.x * 10000 + p.y; };
	for (Point &p : points) {
		cin >> p;
		seen[hash(p)] = true;
	}
 
	// Check if point lies inside the grid
	auto inside = [&](const Point &p) -> bool {
		return 1 <= p.x && 1 <= p.y && p.x <= r && p.y <= c;
	};
 
	// Sort the points
	sort(points.begin(), points.end());
	int ans = 0;
	for (int i = 0; i < points.size(); i++) {
		for (int j = i + 1; j < points.size(); j++) {
			// The distance between the equally-spaced points
			Point diff = points[j] - points[i];
 
			// Check if the left point lies outside the grid
			// This way we avoid processing the same line multiple times
			Point left = points[i] - diff;
			if (inside(left)) { continue; }
 
			// The point that continues the line
			Point right = points[j] + diff;
			int hops = 2;
			while (seen[hash(right)]) {
				right = right + diff;
				hops++;
			}
 
			/*
			 * If the final point lies outside the grid
			 * it means that the frog left the grid,
			 * making the line valid
			 */
			if (!inside(right) && hops > 2) { ans = max(ans, hops); }
		}
	}
 
	cout << ans << endl;
}
Fundamentos