Editing Convex hull trick
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
==History== | ==History== | ||
− | The convex hull trick is perhaps best known in algorithm | + | The convex hull trick is perhaps best known in algorithm competition from being required to obtain full marks in several USACO problems, such as [http://tjsct.wikidot.com/usaco-mar08-gold MAR08 "acquire"], which began to be featured in national olympiads after its debut in the IOI '02 task {{problem|ioi0221|Batch Scheduling}}, which itself credits the technique to a 1995 paper (see references). Very few online sources mention it, and almost none describe it. It has been suggested (van den Hooff, 2010) that this is because the technique is "obvious" to anybody who has learned the [[sweep line algorithm]] for the [[line segment intersection problem]]. |
==The problem== | ==The problem== |