What is the best algorithm for querying the number of points in a triangle? Given that there are n points and q queries.

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

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 166 |

4 | antontrygubO_o | 165 |

4 | Vovuh | 165 |

6 | rng_58 | 161 |

7 | majk | 156 |

7 | Um_nik | 156 |

9 | 300iq | 155 |

10 | tourist | 153 |

What is the best algorithm for querying the number of points in a triangle? Given that there are n points and q queries.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/14/2019 20:13:55 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Pick's theorem can help you, which count total integral point inside triangle

That's not his question

You can break down a triangle query to a constant amount of "ray" queries; how many points are under a ray. Specifically let's break it to "prefix" rays — those which extend infinitely to the left.

If we sort the points according to x-axis, then the prefix ray queries become queries to count points under a line inside some prefix. Let's break the array to $$$\frac{N}{K}$$$ blocks of size $$$K$$$. For the tail of the prefix query (the cells which are not in a complete block), count normally in $$$\mathcal{O}(K)$$$. As for the blocks, you can do some precomputation described nicely here. You end up with $$$\mathcal{O}(\sqrt{N} \cdot polylog N)$$$ per query for an optimal choice for $$$K$$$ (the polylog depends on how you implement whichever approach is described in the linked post). This approach is probably not noticeably faster for acceptable values of $$$N, Q$$$, but at least it's sublinear.

Also, this works online, but if you allow yourself offline then you can do cuts on complexities, some shown in the linked post, and some can be done here to cut down memory a lot (build the structure per block on its own, and move to the next one using the same memory, for instance).