Project Euler 143 Investigating the Torricelli point of a triangle

开启传送门

题目描述

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.

题意

就是三个角都小于120度的三角形存在费马点,然后让你找到所有这样的三角形,使得图上对应的六条边都是整数,其中$T$就是费马点.然后你要找到所有$p+q+r$不同的所有三角形,然后把$p+q+r$求和.

分析

对于每一个圆来说,因为里面的三角形是对边三角形,然后因为$T$在园上,于是有$T$对应的角大小一定是$180-60 = 120$度,然后同理可得,三个角都是$120$度,然后我们运用余弦定理可以得到$p^2+q^2+pq=b^2$,因为我们只要$p+q+r$不同的解,所以我们不妨设$p>=q>=r$,因为三个角都是$120$度,所以余弦定理都成立,所以我们可以得到

\begin{eqnarray}
q^2+r^2+qr &= a^2\\
p^2+q^2+pq &= b^2\\
p^2+r^2+pr &= c^2\\
p>=q>=r\\
\end{eqnarray}

然后我们对于每对关系,可以显然发现都应该是类似的,然后我们可以存下来每个关系,然后暴搜就行了,emmmmmm$\dots$

代码

给大佬递上我奇丑无比的代码　(/ω＼)

#include<bits/stdc++.h>
using namespace std;
const int upper = 1.2e5;
set<int> to[upper+10];
bool ans[upper<<2];
int main(){
	for(long long i = 1;i<=upper;i++){
		for(long long j = min(upper-i,i);j>=1;j--){
			long long x = i*i+j*j+i*j;
			long long y = sqrt(x);
			if(y*y==x) to[i].insert(j);
		}
		if(i%10==0) cout<<i<<'\n';
	}
	for(int i = 1;i<=upper;i++){
		for(int j:to[i]){
			for(int k:to[j]){
				if(i+j+k>upper) continue;
				if(to[i].count(k)){
					ans[i+j+k] = true;
				}
			}
		}
	}
	int rans = 0;
	for(int i = 1;i<=upper;i++) if(ans[i]) rans+=i;
	cout<<rans<<endl;
	return 0;
}