首先,对Topcoder的信用,因为这个问题在他们的一个SRM中使用(但他们没有编辑...)
在这个问题中,我给了n个点(其中n在1到1000之间).对于每三个点,显然有一个连接它们的三角形.问题是,这些三角形中有多少包含点(0,0).
我试过在堆栈上查看这个线程:
但是我无法理解使用什么数据结构/如何使用它们来解决这个问题.
这个问题的一个明显天真的解决方案是使用低效的O(n ^ 3)算法并搜索所有点.但是,有人可以帮助我提高效率,并在O(n ^ 2)时间内完成此操作吗？
以下是Petr解决这个问题的方法......它很短,但有一个我无法理解的大创意.
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class TrianglesContainOrigin {
public long count(int[] x, int[] y) {
int n = x.length;
long res = (long) n * (n - 1) * (n - 2) / 6;
for (int i = 0; i < n; ++i) {
int x0 = x[i];
int y0 = y[i];
long cnt = 0;
for (int j …