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

Investigating the Torricelli point of a triangle 题号:143 难度: 65 中英对照

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XC = q, and XB = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r ≤ 120000 for Torricelli triangles.


Solution

显然费马点与三角形三个顶点的连线夹角都是120度。 考虑三角形ATB,注意到边长为$p,r,c$,顶角T是120度。 由余弦定理得到: $$c^2=p^2+r^2+pr$$ 要使得$p,r,c$都是整数,则$p^2+r^2+pr$是完全平方数。 同理可得: $$c^2=p^2+r^2+pr$$ $$a^2=q^2+r^2+qr$$ $$b^2=p^2+q^2+pq$$ 则按照以下步骤: 1. 找到所有满足$x^2+y^2+xy$是完全平方数且$x+y\leq 120000$的二元组$(x,y)$ 2. 对上述所有二元组搜索来找到对应的$(a,b,c)$满足$(a,b)(a,c)(b,c)$都属于上述二元组 3. 如果发现$(a,b,c)$满足$a+b+c\leq 120000$则做上标记 4. 对所有做了标记的数字累和 需要注意的是: 第一,步骤1需要进行优化: 对于任意的整数$u,v$,满足$u \geq v, \quad u-v \neq 0 (mod\quad 3)$则可以得到一个三元组 $$p=2uv+v^2,r=u^2-v^2,c=u^2+v^2+uv$$ 这使得$c=u^2+v^2+uv$是整数。 于是我们利用该结论直接生成$u,v$,然后求解$p,r$即为所需二元组。 注意这个搜索限制只需要在$u^2\leq 120000$即可。 第二,步骤2需要进行优化: 对二元组进行排序,利用一个index数组来记录二元组中第一维在有序数组中第一次出现的位置。 搜索时只需要枚举一个二元组$(x,y)$,并将所有第一维等于$x$的放入一个序列,将所有第二维等于$y$的放入另一个序列,然后枚举前一个序列,判断其是否在后一个序列中出现,即可得到三元组。

Code

public final class p143 {
    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 class Pair implements Comparable<Pair>{
    	int x,y;
    	public Pair(int x,int y){
    		this.x=x;this.y=y;
    	}
		public int compareTo(Pair o) {
			int ans=Integer.compare(x,o.x);
			if(ans!=0) return ans;
			return Integer.compare(y,o.y);
		}
		public boolean equals(Object o){
			if(o==null) return false;
			if(o instanceof Pair) return this.compareTo((Pair)o)==0;
			return false;
		}
		public String toString(){return x+","+y;}
    }
    
    static public String run(){
    	java.util.ArrayList<Pair> pair=new java.util.ArrayList<Pair>();
    	final int LIMIT=120000;
    	for(int u=1;u<347;u++)for(int v=1;v<u;v++){
    		if(gcd(u,v)!=1) continue;
    		if((u-v)%3==0) continue;
    		int a=2*u*v+v*v;
    		int b=u*u-v*v;
    		if(a+b>LIMIT) break;
    		for(int k=1;k*(a+b)<=LIMIT;k++){
    			pair.add(new Pair(k*a,k*b));
				pair.add(new Pair(k*b,k*a));
    		}
    	}
    	java.util.Collections.sort(pair);
    	boolean vis[]=new boolean[LIMIT+1];
    	for(int i=0;i<vis.length;i++) vis[i]=false;
    	//vis用来去重
    	int index[]=new int[LIMIT+1];
    	for(int i=0;i<index.length;i++) index[i]=-1;
    	for(int i=0;i<pair.size();i++){
    		int x=pair.get(i).x;
    		if(index[x]==-1)
    			index[x]=i;
    	}//index[i]是标记pair中元素i开始的起点
    	for(int i=0;i<pair.size();i++){
    		Pair p=pair.get(i);
    		int a=p.x;
    		java.util.ArrayList<Integer> va=new java.util.ArrayList<Integer>();
    		for(int j=index[a];j<pair.size();j++){
    			Pair q=pair.get(j);
    			if(q.x!=a) break;
    			va.add(q.y);
    		}
    		int b=p.y;
    		java.util.ArrayList<Integer> vb=new java.util.ArrayList<Integer>();
    		for(int j=index[b];j<pair.size();j++){
    			Pair q=pair.get(j);
    			if(q.x!=b) break;
    			vb.add(q.y);
    		}
    		for(int c:va){
    			if(vb.contains(c) && a+b+c<=LIMIT)
    				vis[a+b+c]=true;
    		}
    	}
    	long sum=0;
    	for(int i=0;i<vis.length;i++) if(vis[i]) sum+=i;
    	return ""+sum;
 	}
 // Returns the largest non-negative integer that divides both x and y.
 	public static int gcd(int x, int y) {
 		while (y != 0) {
 			int z = x % y;
 			x = y;
 			y = z;
 		}
 		return x;
 	}

}
30758397
1451ms