ceoi_tri 대회 풀이
Solution for “tri”
The brute-force solution, earning 20 points, runs in O(K·M) time. For each pair (query point, triangle), one can check in constant time whether the point is inside the triangle, using elementary geometric calculations.
Special case: right triangles. As stated in the problem text, one can obtain 50 points by only dealing with triangles that have one edge on the x-axis, and another on the y-axis. The solution runs in O((K + M) ∙ lg K) time.
First, one can find the set S of points on the convex hull which are visible from the origin. This can be done in O(K ∙ lg K) using any convex hull algorithm. Subsequently, each triangle query can be answered in O(lg K) time – we can use binary search to test whether a line intersects a convex polygon. The details are simple: for each line, the normal to the line is described by a linear function f: R2 → R, f(x,y) = a·x + b·y + c. It is easy to see that the function is unimodal on a convex set of points. Thus, we can use a variation of binary search to find the minimum of the function. If any point is inside the triangle, the minimum point must be inside.
The general case. Generalizing this solution to arbitrary triangles uses divide and conquer. First, we sort the K points by polar angle. Now consider a balanced binary tree over the points. In each node, we only care about the convex hull of the points appearing in the node’s subtree (as before, only those visible from the origin).
A triangle is decomposed into O(lg K) triangles; each one spans a node of the binary tree. Thus, inside each node we only need to compare the points with the third triangle side (the one not containing the origin). For that, we can use the binary search solution from the special case.
Overall, the time complexity is O((K + M) ∙ lg2K), which earns 100 points. It is possible to further improve the solution to O(sort(K+M) · lg K), where sort(N) denotes the time to sort N numbers. Indeed, the complexity of convex hull is equal to sorting, and the binary search can be replaced by sorting (sort all lines by slope, and then “merge” them with the points of the convex hull in linear time). By using radix sort for sorting, the running time is improved significantly. However, this improvement is not needed for a maximal score.
Test cases. In the test cases for the special case, most points are on the convex hull (with a few points that don't matter inside the hull). The queries are tangents to the convex hull, either moved “in” (to make the answer yes), or “out” (to make the answer no).
For the general case, we have two similar strategies:
1. We generate sqrt(N) “top level” points in convex position. Between any consecutive pair (looking at the angle from the origin), we insert sqrt(N) “bottom level” points. The bottom points are also in convex position, and further out than the top-level points. For the queries, we draw tangents, either to the top convex hull, or to a random bottom convex hull.
2. We consider an array A[1..K], where every A[i] has value x with probability O(2-x). We consider a random line, and transform each A[i] into a point shifted inside from the line by ~ A[i]. The data looks like O(lg K) nested hulls, each having few points. For the triangles, we pick a random level, and take a tangent to a hull of that level.
