NC223536. GoneFishing
描述
输入描述
The first input line provides the radius of the circle. The second input line contains an integer, n (1 ≤ n ≤ 100), indicating the number of fish. Each of the next n input lines provides the location (x,y) for one fish.
Assume all these points are distinct. Also assume that all the x and y values in the input (as well as the circle radius) are integers between 1 and 1000, inclusive.
输出描述
Print the maximum fish Floyd can catch with one throw.
示例1
输入:
20 4 6 7 5 5 190 100 4 4
输出:
3
示例2
输入:
3 2 1 1 95 4
输出:
1
C++ 解法, 执行用时: 15ms, 内存消耗: 436K, 提交时间: 2021-08-12 07:06:29
#include<bits/stdc++.h>
using namespace std;
int n, ans = 1;
double r, x[123], y[123], d, k, xc, yc, dx, dy;
int f(double xr, double yr)
{
int ans = 0;
for(int i = 0; i < n; i++)
ans += hypot(x[i]-xr, y[i]-yr) <= r+1e-6;
return ans;
}
int main()
{
cin >> r >> n;
for(int i = 0; i < n; i++)
cin >> x[i] >> y[i];
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{
d = hypot(x[i]-x[j], y[i]-y[j]);
xc = (x[i]+x[j]) / 2, yc = (y[i]+y[j]) / 2;
dx = x[j] - x[i], dy = y[j] - y[i];
k = sqrt(r*r-d*d/4) / hypot(dx, dy);
ans = max(ans, f(xc-dy*k, yc+dx*k));
}
cout << ans;
}