3929 - 打地鼠
每秒会有一个地鼠从一个点冒头，你从一个点移动到另一个点需要花费值为欧几里得距离的平方能量，每秒不移动的情况下能
回复100点能量（能量不能超过最大值），求最多能连续打到的地鼠数量。初始能量为最大值S
题目输入
输入一个T表示T组数据，接下来输入一个n和一个S表示有n(n<=1000)个地鼠，能量最大值为S(S<=100000)，接下来n行，第i行表示输入两个整数Xi，Yi，表示第i秒有一个地鼠在Xi和Yi出现。(-1000<=xi,yi<=1000)。你可以从任意坐标还是行动
题目输出
对于每组数据输出一个数表示最多能连续打到的地鼠数量
输入/输出样例
题目输入
2 5 1 0 0 0 1 0 2 3 3 4 4 5 0 0 0 0 1 0 2 3 3 4 4
题目输出
2 1
C++解答
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; struct P { int x,y; }a[1005]; int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int t; scanf("%d",&t); while(t--) { int n,S; scanf("%d%d",&n,&S); for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); int sum=1; for(int i=0;i<n;i++) { int res=S; int temp=1; for(int j=i+1;j<n;j++) { int p=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y); if(res>=p) { res-=p; temp++; } else break; } sum=max(sum,temp); } printf("%d\n",sum); } }