[TIOJ] 1289. E.畢氏煩惱

題目連結:http://tioj.infor.org/problems/1289
N小小的,所以直接枚舉兩條邊,再看看他的第三邊存不存在就好,至於要如何快速看第三邊存不存在,可以考慮用個unordered_set存下每個邊的平方
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

lld arr[2000];
unordered_set<lld> isset;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		isset.clear();
		for(int i=0;i<n;i++) cin>>arr[i];
		sort(arr,arr+n);
		int st;
		for(st=0;st<n&&arr[st]<=0;st++);
		for(int i=st;i<n;i++) isset.insert(arr[i]*arr[i]);
		int ans=0;
		for(int i=st;i<n;i++) for(int j=i+1;j<n;j++)
			if(isset.find(arr[i]*arr[i] + arr[j]*arr[j]) != isset.end())
				ans++;
		cout<<ans<<'\n';
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology