题意分析

题目描述了一个制作巧克力曲奇饼干的过程，其中关注的是面团擀平后切出第一块曲奇的过程。给定巧克力碎片在曲奇面团平面上的坐标，要求放置一个直径为 $5$ 厘米的圆形模具，使其边缘内包含的巧克力碎片数量最大化。输入是多个巧克力碎片的坐标，输出是模具边缘内所能包含的巧克力碎片的最大数量。

解题思路

1. 理解问题：我们需要找到一个直径为 $5$ 厘米的圆，使得这个圆的边缘内包含的巧克力碎片数量最多。这个问题可以转化为在平面上找到一个半径为 $2.5$ 厘米的圆，使得这个圆内包含的点数最多。

2. 数据结构：使用一个列表来存储所有巧克力碎片的坐标。

3. 算法设计：

   • 暴力法：对于每个巧克力碎片，以它为中心画一个半径为 $2.5$ 厘米的圆，然后计算这个圆内包含的巧克力碎片数量。最后取所有数量中的最大值。这种方法的时间复杂度是 $O(n^2)$，其中 $n$ 是巧克力碎片的数量。
   • 优化：考虑到巧克力碎片的数量最多为 $200$，暴力法在可接受的时间内可以完成计算。

4. 实现细节：

   • 使用一个函数来计算两个点之间的距离：$$\text{distance}(p_1, p_2) = \sqrt{(p_1[0] - p_2[0])^2 + (p_1[1] - p_2[1])^2} $$
   • 遍历每个巧克力碎片，以它为中心计算圆内包含的巧克力碎片数量。
   • 保持一个变量来记录最大数量。

   ---

标程

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point {
    double x, y;
    Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
};

double distanceSquared(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
}

int maxCookies(vector<Point>& points) {
    const double r = 2.5;
    const double rSquared = r * r;
    int maxCount = 0;
    int n = points.size();

    // Check circles centered at each point
    for (int i = 0; i < n; ++i) {
        int count = 0;
        for (int j = 0; j < n; ++j) {
            if (distanceSquared(points[i], points[j]) <= rSquared + 1e-8) {
                ++count;
            }
        }
        if (count > maxCount) {
            maxCount = count;
        }
    }

    // Check circles passing through pairs of points
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Point a = points[i];
            Point b = points[j];
            double dSquared = distanceSquared(a, b);
            if (dSquared > 4 * rSquared + 1e-8) {
                continue; // Distance more than diameter, skip
            }
            double d = sqrt(dSquared);
            Point mid((a.x + b.x) / 2, (a.y + b.y) / 2);
            if (d < 1e-8) {
                continue; // Same point, skip
            }
            double h = sqrt(rSquared - (d / 2) * (d / 2));
            // Perpendicular direction
            double perpX = -(b.y - a.y);
            double perpY = b.x - a.x;
            // Normalize
            double perpLength = sqrt(perpX * perpX + perpY * perpY);
            perpX /= perpLength;
            perpY /= perpLength;
            // Two possible centers
            Point center1(mid.x + h * perpX, mid.y + h * perpY);
            Point center2(mid.x - h * perpX, mid.y - h * perpY);
            // Count points for center1
            int count1 = 0;
            for (int k = 0; k < n; ++k) {
                if (distanceSquared(center1, points[k]) <= rSquared + 1e-8) {
                    ++count1;
                }
            }
            if (count1 > maxCount) {
                maxCount = count1;
            }
            // Count points for center2
            int count2 = 0;
            for (int k = 0; k < n; ++k) {
                if (distanceSquared(center2, points[k]) <= rSquared + 1e-8) {
                    ++count2;
                }
            }
            if (count2 > maxCount) {
                maxCount = count2;
            }
        }
    }

    return maxCount;
}

int main() {
    vector<Point> points;
    double x, y;
    while (cin >> x >> y) {
        points.push_back(Point(x, y));
    }
    cout << maxCookies(points) << endl;
    return 0;
}