解题思路

本题要求在凸多边形的非相邻顶点间连接最多的不相交绳子，且绳子不能穿过任何圆形麦田圈。解题核心是结合几何判断与动态规划（DP），步骤如下：

1. 几何合法性判断

对于任意两个非相邻顶点 (i) 和 (j)，判断线段 (i-j) 是否与所有麦田圈相交或相切：

• 端点在圆内：若顶点到圆心的距离 ≤ (R)，线段不合法。
• 线段与圆相交：计算圆心到线段的垂直距离 (h)，若 (h ≤ R)，线段不合法。
  通过余弦定理避免直接计算垂足坐标，引入极小量（如 (1e-10)）处理浮点精度问题。

2. 凸多边形顶点排序

将顶点按顺时针或逆时针顺序排列以便动态规划处理：

• 先按坐标排序找到最左下方的顶点（设为顶点 1）。
• 以顶点 1 为基准，按极角排序其他顶点，确保顺序一致。

3. 动态规划求解

定义 (f[start][end]) 表示从顶点 (start) 到 (end) 构成的子多边形中能连接的最多合法不相交边数。状态转移方程为：
[ f[start][end] = \max_{start < k < end} { f[start][k] + f[k][end] } + \text{ok}[start][end] ]
其中 (\text{ok}[start][end]) 标记 (start) 和 (end) 间是否存在合法边。枚举中间点 (k)，将子多边形划分为两部分，累加最优解并更新当前状态。

标准程序代码

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
bool ok[255][255];
int n,g,r,f[255][255];
struct Point{int x,y;}point[255];
struct Circle{int x,y;}circle[255];
bool check(int a,int b){
    double sx=1.0*point[a].x,sy=1.0*point[a].y;
    double ex=1.0*point[b].x,ey=1.0*point[b].y;
    double C=sqrt(1.0*(sy-ey)*(sy-ey)+1.0*(sx-ex)*(sx-ex));
    for(int i=1;i<=g;i++){
        double A=sqrt((circle[i].x-sx)*(circle[i].x-sx)+(circle[i].y-sy)*((circle[i].y-sy)));
        double B=sqrt((circle[i].x-ex)*(circle[i].x-ex)+(circle[i].y-ey)*((circle[i].y-ey)));
        double COSA=(B*B+C*C-A*A)/(2*B*C);
        double COSB=(A*A+C*C-B*B)/(2*A*C);
        if(COSA<1e-10||COSB<1e-10){
            if(A<1.0*r+1e-10||B<1.0*r+1e-10)return 0;
            else continue;
        }
        double SINA=sqrt(1-COSA*COSA);
        double H=B*SINA;
        if(H<1.0*r+1e-10)return 0;
    }
    return 1;
}
bool cmp(Point a,Point b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
bool cmp2(Point a,Point b){return (long long)(a.x-point[1].x)*(b.y-point[1].y)-(long long)(a.y-point[1].y)*(b.x-point[1].x)>0;}
int main(){
    scanf("%d%d%d",&n,&g,&r);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&point[i].x,&point[i].y);
    sort(point+1,point+1+n,cmp);
    sort(point+2,point+1+n,cmp2);
    for(int i=1;i<=g;i++)
        scanf("%d%d",&circle[i].x,&circle[i].y);
    for(int i=1;i<=n;i++)
        for(int j=i+2;j<=n;j++)
            if(check(i,j)&&(i!=1||j!=n))ok[i][j]=1;
    for(int lenth=2;lenth<=n;lenth++)
        for(int start=1;start<=n;start++){
            int end=start+lenth;
            if(end>n+1)end-=n;
            for(int k=start+1;k<min(end,n+1);k++){
                int real_k=k>n?k-n:k;
                f[start][end]=max(f[start][end],f[start][real_k]+f[real_k][end]);
            }
            f[start][end]+=ok[start][end];
        }
    printf("%d\n",f[1][n]);
}

代码说明

• 几何判断函数 check：通过计算端点到圆心的距离和垂直距离，判断线段是否合法。
• 排序处理：cmp 和 cmp2 确保顶点按顺时针/逆时针顺序排列，便于动态规划处理。
• 动态规划：枚举子多边形长度和中间点，逐步构建最优解，最终结果存储在 (f[1][n]) 中。

此程序通过预处理合法性和动态规划高效求解，适用于 (N \leq 150) 的规模。