Pontos aleatórios diferentes de uma grade bidimensional

Eu tenho uma grade grande de 2 dimensões, digamos 10000 X 10000. A partir dessas grades eu preciso selecionar 1000 pontos aleatórios, mas também preciso ter cuidado para que nenhum dos dois pontos seja o mesmo. A maneira padrão que vem à minha mente é depois de selecionar cada ponto que eu deveria verificar todas as entradas anteriores para ver se esse ponto já foi selecionado ou não, mas parece que para grandes redes e grande número de pontos isso se tornará ineficiente. Tem algum jeito melhor de fazer isso? Estou usando o C ++

questionAnswers(3)

yourAnswerToTheQuestion