当前位置:首页 » Project Euler » 详细页

Triangles containing the origin 题号:184 难度: 75 中英对照

Consider the set Ir of points (x,y) with integer co-ordinates in the interior of the circle with radius r, centered at the origin, i.e. x2 + y2 < r2.

For a radius of 2, I2 contains the nine points (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1) and (1,-1). There are eight triangles having all three vertices in I2 which contain the origin in the interior. Two of them are shown below, the others are obtained from these by rotation.

For a radius of 3, there are 360 triangles containing the origin in the interior and having all vertices in I3 and for I5 the number is 10600.

How many triangles are there containing the origin in the interior and having all three vertices in I105?


Solution

考虑对每一个点A(不同于原点O),AO连线上不含A也不含O的点有s个,连线一侧有a个点,显然另一侧点的个数也等于a。 检查以A为顶点的三角形,将对称的情况$\times 2$以便后续直接$/6$即可(三角形的三个点会重复计算三次贡献,再加上对称)。 $$2\times a\times a-C_a^2\times 2$$ 上式表示了所有对称的情况$\times 2$和所有不对称的情况$\times 1$(不对称的情况被后一项减去了)。 接下来判定原点O的位置关系: 由于是整体考虑,所以针对点A构建三角形AMN时,可以站在M点的角度考虑,对于任意一侧的a个M点而言,需要减去的情况不外乎: AN对称且过原点$\times 2$,AN对称但AMN不包含原点$\times 2$,AN不对称且过原点$\times 1$,AN不对称但AMN不包含原点$\times 1$ 首先,注意到最后一项为0,因为从A的角度看来MN是同一侧的,并没有被计算过。 其次,用$(s+1)/2$来表示OA连线去除OA射线之后的线上的点的个数,这些点作为点N时AN过原点,所以需要在答案中减去$(s+1)/2\times a$ 此时还剩下需要减去的项有: AN对称且过原点$\times 1$,AN对称但AMN不包含原点$\times 2$ 将第二项拆开有: AN对称且过原点$\times 1$,AN对称但AMN不包含原点$\times 1$,AN对称但AMN不包含原点$\times 1$ 注意第三项,对称的情况下包含或不包含原点的情况是对称的,所以可改写为: AN对称且过原点$\times 1$,AN对称但AMN不包含原点$\times 1$,AN对称但AMN包含原点$\times 1$ 这就是AN对称的所有情况,种数为a。 所以每个点对答案的贡献是 $$2\times a\times a-C_a^2\times 2 \quad -(s+1)/2\times a -a$$

Code


public final class p184 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    

	static int R = 105;
	static point[] Lattice = new point[4 * R * R];
	static long[] straight = new long[4 * R * R];
	static int Ln = 0;

	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	static point Origin = new point(0, 0);

    static public String run() {
		for (int x = 0; x < R; x++)
			for (int y = 0; y < R; y++)
				if (x * x + y * y < R * R && !(x == 0 && y == 0)) {
					Lattice[Ln++] = new point(x, y);
					if (x > 0)
						Lattice[Ln++] = new point(-x, y);
					if (y > 0)
						Lattice[Ln++] = new point(x, -y);
					if (x > 0 && y > 0)
						Lattice[Ln++] = new point(-x, -y);
				}
		for (int i = 0; i < Ln; i++) {
			point curr = Lattice[i];
			if (curr.x == 0)
				straight[i] = 2 * (R - 1) - 1;
			else {
				int count = 0;
				int x = curr.x, y = curr.y, c = gcd(x, y);
				x /= c;
				y /= c;
				for (int jx = x;; jx += x) {
					int jy = jx / x * y;
					if (jx * jx + jy * jy >= R * R)
						break;
					count++;
				}
				straight[i] = 2 * count - 1;
			}
		}
		long ans = 0;
		for (int i = 0; i < Ln; i++) {
			long s = straight[i], a;
			a = (Ln - s) / 2;
			ans += 2 * a * a - a * (a - 1) - (s+1)*a/2-a;
		}
		return (ans/6)+"";
	}
    
    static class point {
    	int x, y;

    	public point() {
    	}

    	public point(int xx, int yy) {
    		x = xx;
    		y = yy;
    	}
    }
    
    
}
1725323624056
11ms