题目大意：给出m和s, 再给出m种电子硬币，每种硬币有两种金额xi,yi。现在要在m种硬币种选若干个硬币，可以重复选同一种硬币， 使得（x1 + x2 + .... + xn) ^ 2 + (y1 + y2 + ... + yn) ^ 2 == s * s, 要求n尽量小，（n为选取硬币的个数）， 如果不能选出满足条件的硬币，输出-1。
解题思路：二维的完全背包问题，注意要用long long。
#include <stdio.h>
#include <string.h>
const int N = 305; struct coin{
int x;
int y;
}val[50];
int n, s, S, dp[N][N]; void read() {
memset(val, 0, sizeof(val));
scanf("%d%d", &n, &s);
S = s * s;
for (int i = 0; i < n; i++)
scanf("%d%d", &val[i].x, &val[i].y);
} int solve() {
int cnt = 1 << 30;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int k = 0; k < n; k++) {
for (int i = 0; i <= s; i++) {
for (int j = 0; j <= s; j++) {
if (dp[i][j]) {
int p = i + val[k].x, q = j + val[k].y;
if (p > s || q > s) break;
if (dp[p][q] == 0 || dp[i][j] + 1 < dp[p][q])
dp[p][q] = dp[i][j] + 1;
if (p * p + q * q == S && dp[p][q] < cnt)
cnt = dp[p][q];
}
}
}
}
if (cnt == 1 << 30) return 0;
else return cnt;
} int main() {
int cas;
scanf("%d", &cas);
while (cas--) {
read();
int ans = solve();
if (ans)
printf("%d\n", ans - 1);
else
printf("not possible\n");
}
return 0;
}