Skip to Content
CTRL K

Mountain View

Análisis oficial (C++) 

Explicación

Notemos que una montaña queda oculta por otra si y solo si la base de la montaña (el área que ocupa en el suelo) está contenida dentro de la base de la otra montaña.

Sin embargo, recorrer todos los pares de montañas y comprobar si una queda oculta por otra toma O(N2)\mathcal{O}(N^2) tiempo y es demasiado lento dado el tamaño de la entrada.

Para acelerarlo, ordenemos las montañas primero por su extremo izquierdo y luego recorramos todas, llevando el extremo derecho más a la derecha que hayamos visto. Entonces, si el lado derecho de la montaña actual es menor que el extremo derecho más alto actual, sabemos que esa montaña queda oculta por otra.

Implementación

Complejidad temporal: O(nlog⁡n)\mathcal{O}(n\log n)

#include <bits/stdc++.h>
using namespace std;
 
struct Mountain {
	int start, end;
};
 
bool operator<(const Mountain &m1, const Mountain &m2) {
	// ordenamos por inicio y, en empate, ponemos primero las montañas más grandes
	if (m1.start == m2.start) { return m1.end > m2.end; }
	return m1.start < m2.start;
}
 
int main() {
	std::ifstream read("mountains.in");
	int mountain_num;
	read >> mountain_num;
 
	vector<Mountain> mountains;
	for (int m = 0; m < mountain_num; m++) {
		int x, y;
		read >> x >> y;
		// guardamos las montañas por el intervalo que cubren
		mountains.push_back({x - y, x + y});
	}
	sort(mountains.begin(), mountains.end());
 
	int rightmost = -1;
	int visible_num = 0;
	for (const Mountain &m : mountains) {
		if (m.end > rightmost) {
			visible_num++;
			rightmost = m.end;
		}
	}
 
	std::ofstream("mountains.out") << visible_num << endl;
}
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Mountains {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("mountains.in"));
		int mountainNum = Integer.parseInt(br.readLine());
 
		Mountain[] mountains = new Mountain[mountainNum];
		for (int m = 0; m < mountainNum; m++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			// guardamos las montañas por el intervalo que cubren
			mountains[m] = new Mountain(x - y, x + y);
		}
		Arrays.sort(mountains);
 
		int rightmost = -1;
		int visibleNum = 0;
		for (Mountain m : mountains) {
			if (m.end > rightmost) {
				visibleNum++;
				rightmost = m.end;
			}
		}
 
		PrintWriter pw = new PrintWriter("mountains.out");
		pw.println(visibleNum);
		pw.close();
	}
}
 
class Mountain implements Comparable<Mountain> {
	public int start, end;
 
	public Mountain(int start, int end) {
		this.start = start;
		this.end = end;
	}
 
	public int compareTo(Mountain other) {
		// ordenamos por inicio y, en empate, ponemos primero las montañas más grandes
		if (this.start != other.start) {
			return Integer.compare(this.start, other.start);
		}
		return Integer.compare(other.end, this.end);
	}
}
class Mountain:
	def __init__(self, start: int, end: int):
		self.start = start
		self.end = end
 
	def __lt__(self, other: "Mountain"):
		# ordenamos por inicio y, en empate, ponemos primero las montañas más grandes
		if self.start == other.start:
			return self.end > other.end
		return self.start < other.start
 
 
with open("mountains.in") as read:
	mountain_num = int(read.readline())
	mountains = []
	for _ in range(mountain_num):
		x, y = [int(i) for i in read.readline().split()]
		# guardamos las montañas por el intervalo que cubren
		mountains.append(Mountain(x - y, x + y))
 
mountains.sort()
 
rightmost = -1
visible_num = 0
for m in mountains:
	if m.end > rightmost:
		visible_num += 1
		rightmost = m.end
 
print(visible_num, file=open("mountains.out", "w"))
Fundamentos