I have another geometry problem: N points on the plane are given and Q querys must be answered. Each query is about computing how many of those points lay inside a circunference. N,Q<=10^4

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | cry | 148 |

6 | SecondThread | 148 |

9 | Petr | 147 |

10 | nor | 145 |

I have another geometry problem: N points on the plane are given and Q querys must be answered. Each query is about computing how many of those points lay inside a circunference. N,Q<=10^4

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 19:47:34 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

There could be a lot of approaches — building sorted view of points by one or both coordinates, dividing set into square cells and then judging for each query which cells are enclosed completely etc.

Which variants you tried yourself and what difficulties you encountered?

I thought something like that but the problem is that the coordinates are x,y<=10^6

No problem, compress the coordinates, and divide the set into squares using the compressed ones. The other option is using a kd-tree to store the points, to answer the queries, each time you visit a node check if its bounds cut the circle (if not exit the subtree), or if it is completely contained whitin it, then continue exploring the subtree or add all the points on the subtree.

In the given constraints (N, Q <= 10^4 ) stupid solution O(Q * N) can be fast enough, don't use square root operation, compare squares of the distances.

I already try that but I got tle