C++ 解法, 执行用时: 3198ms, 内存消耗: 1400K, 提交时间: 2022-04-20 23:55:57

#include <bits/stdc++.h>

using namespace std;
const int N = 3000 + 10;
const double PI = acos(-1);

struct Point {
    double x, y;

    Point operator-(const Point &b) {
        return {x - b.x, y - b.y};
    }

    //点乘
    double operator^(const Point &b) {
        return x * b.x + y * b.y;
    }

    //差乘
    double operator*(const Point &b) {
        return x * b.y - y * b.x;
    }
} p[N];


signed main() {
    //freopen("./data.in", "r", stdin);
    //freopen("./data.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    double t;
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    int ans = 2;
    Point X = {1, 0};
    //原点
    for (int i = 1; i <= n; i++) {
        //0,pi
        vector<pair<double, int>> vec;
        for (int j = 1; j <= n; j++) {
            if (i == j)continue;
            Point v = p[j] - p[i];
            double lenV = sqrt(v ^ v);
            double ang = acos(1.0 * (X ^ v) / lenV);
            if (X * v < 0) {
                ang = 2 * PI - ang;
            }
            vec.push_back({ang - PI, 1});
            vec.push_back({ang, -1});
            if (lenV > t) {
                double angD = asin(t / lenV);
                vec.push_back({ang - PI + angD, -1});
                vec.push_back({ang - angD, 1});
            }

        }
        sort(vec.begin(), vec.end());
        int sum = 1;
        for (auto v: vec) {
            //cout << v.first << " " << v.second << "\n";
            ans = max(ans, sum += v.second);
        }
    }
    cout << ans;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3019ms, 内存消耗: 1072K, 提交时间: 2022-10-06 14:45:44

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define _for(i,L,R) for(int i=L;i<=R;++i)
//#define int long long

using namespace std;
using db=double;
const db pi=acos(-1);
using node=pair<db,db>;
#define x first
#define y second

node operator-(node a,node b)
{
	return {a.x-b.x,a.y-b.y};
}

db dot(node a,node b)
{
	return a.x*b.x+a.y*b.y;
}

db cross(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}

int maxnum_fixed_length_ribbon_cover_point(const vector<node> & p,double wid)
{
	int res = 2,n=p.size();
    node X = {1, 0};
    for (int i = 0; i < n; i++) {
        vector<pair<double, int>> vec;
        for (int j = 0; j < n; j++) {
            if (i == j)continue;
            node v = p[j] - p[i];
            double lenV = sqrt(dot(v,v));
            double ang = acos(1.0 * dot(X,v) / lenV);
            if (cross(X,v) < 0) ang = 2 * pi - ang;
            vec.push_back({ang - pi, 1});
            vec.push_back({ang, -1});
            if (lenV > wid) {
                double angD = asin(wid / lenV);
                vec.push_back({ang - pi + angD, -1});
                vec.push_back({ang - angD, 1});
            }
        }
        sort(vec.begin(), vec.end());
        int sum = 1;
        for (auto v: vec) res = max(res, sum += v.second);
    }
    return res;
}

signed main()
{
	int n,wid;
	vector<node> p;
	scanf("%d%d",&n,&wid);
	_for(i,1,n){
		db x,y;
		scanf("%lf%lf",&x,&y);
		p.push_back({x,y});
	}
	printf("%d\n",maxnum_fixed_length_ribbon_cover_point(p,wid));
	return 0;
}