Conteggio del numero totale di punti all'interno di 2 cerchi

Question

Ci sono 2 cerchi e i loro centri sono fissi e verranno dati come input. Quindi ci saranno n punti, le cui coordinate xey sono date come input.

Infine, ci saranno q query. Per ogni query, verrà indicato il raggio dei due cerchi (Lasciali essere r1 e r2). Emettere il numero totale di punti all'interno del primo cerchio o del secondo cerchio per ogni query. Un punto si trova all'interno di un cerchio se la distanza dal punto al centro è inferiore o uguale al raggio del cerchio.

Vincoli: n, q < = 10^6 r1, r2 < = 10^7 e per ogni coordinata, | x | e | y | < = 10^6

Sto cercando un algoritmo di pre-elaborazione O (nlogn) o O (nlog^2n) e poi O (logn) per query. O (n) la soluzione per query è troppo lenta. Qualche idea su come rompere questo?

Answer 1

Lascia che C1, C2 siano i centri dei dischi. Lascia che Pi, i = 1 ... n, siano i punti. Sia Qj, j = 1 ... q, sia la query j-esima, Qj = (qj1, qj2).

1. Per ogni punto Pi, calcolare d (Pi, Ck), k = 1 o 2. Inserirlo in una multimappa ordinata: Mk (d (Pi, Ck)) contiene Pi. Questo può essere fatto in O (nlogn) (in realtà è come ordinare l'elenco delle distanze).
2. Per ogni query Qj, eseguire una ricerca binaria per qjk sui tasti di Mk, che può essere eseguita in O (logn).
3. Per ogni query Qj, prendi l'unione dei valori della multimappa sui tasti che sono minori o uguali a quella che hai trovato sopra.

Answer 2

Soluzione con O (log N) tempo di risposta.

1. È facile per ogni query per contare i punti al di fuori di entrambi i cerchi, quindi sottrarre il risultato numero totale di punti.
2. È più facile utilizzare le coordinate cartesiane. In modo che X sarebbe la distanza da C1, Y - la distanza da C2. In questo caso abbiamo solo bisogno di trovare il numero di punti nell'area X > r1 && Y > r2.
3. Assegnare il valore "1" a ciascun punto. Ora abbiamo solo bisogno di trovare la somma dei valori in un'area data. Nel caso 1D questo può essere fatto con l'albero di Fenwick. Ma il caso 2D non è molto diverso se si utilizza l'albero di Fenwick 2D.
4. 2D L'albero di Fenwick deve occupare troppo spazio (10 valori con vincoli dati). Ma l'array 2D per l'albero di Fenwick è molto scarso, quindi potremmo usare una mappa hash per memorizzare i suoi valori e ridurre i requisiti di spazio (e il tempo di pre-elaborazione) a O (N log N).