2 条题解

  • 0
    @ 2025-10-8 16:54:50

    #include <bits/stdc++.h>
    using namespace std;
    const int N=260, N2=90000;
    
    struct node {
        int from, to;
        double x, y;
    } a[N], e[N2]; 
    
    int cnt;
    bool cmp(node a, node b) { //使用atan2(-pi~pi)
        return atan2(a.x, a.y) < atan2(b.x, b.y);
    }
    int f[N2];//dp就是一维的dp,设f[i] 表示当前为第 i 个点时最多能选择多少个
    bool vis[N2];
    int main() {
        int n;scanf("%d", &n);
        for (int i = 1; i <= n; i++)scanf("%lf %lf", &a[i].x, &a[i].y);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)if (i != j) //n ^ 2 建边
                e[++cnt] ={i,j,a[j].x - a[i].x,a[j].y - a[i].y};
        sort(e + 1, e + 1 + cnt, cmp);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            memset(f, 0xc0, sizeof f);
            memset(vis, false, sizeof vis);
            vis[i] = true;
            f[i] = 0;
            for (int j = 1; j <= cnt; j ++) //一个个枚举,保证单调顺序
                if (vis[e[j].from]) {
                    f[e[j].to] = max(f[e[j].to], f[e[j].from] + 1); //可以选可以不选
                    vis[e[j].to] = true;
                }
            ans = max(ans, f[i]);
        }
        printf("%d", ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:54:35
      #include <bits/stdc++.h>
      using namespace std;
      const int N=260, N2=90000;
      
      struct node {
      	int from, to;
      	double x, y;
      } a[N], e[N2]; 
      
      int cnt;
      bool cmp(node a, node b) { //使用atan2(-pi~pi)
      	return atan2(a.x, a.y) < atan2(b.x, b.y);
      }
      int f[N2];//dp就是一维的dp,设f[i] 表示当前为第 i 个点时最多能选择多少个
      bool vis[N2];
      int main() {
      	int n;scanf("%d", &n);
      	for (int i = 1; i <= n; i++)scanf("%lf %lf", &a[i].x, &a[i].y);
      	for (int i = 1; i <= n; i++)
      		for (int j = 1; j <= n; j++)if (i != j) //n ^ 2 建边
                  e[++cnt] ={i,j,a[j].x - a[i].x,a[j].y - a[i].y};
      	sort(e + 1, e + 1 + cnt, cmp);
          int ans = 0;
      	for (int i = 1; i <= n; i++) {
      		memset(f, 0xc0, sizeof f);
      		memset(vis, False, sizeof vis);
      		vis[i] = True;
      		f[i] = 0;
      		for (int j = 1; j <= cnt; j ++) //一个个枚举,保证单调顺序
      			if (vis[e[j].from]) {
      				f[e[j].to] = max(f[e[j].to], f[e[j].from] + 1); //可以选可以不选
      				vis[e[j].to] = True;
      			}
      		ans = max(ans, f[i]);
      	}
      	printf("%d", ans);
      	return 0;
      }
      • 1

      【DP】周长含最多点的凸多边形[USACO08DEC] Largest Fence G

      信息

      ID
      924
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      26
      已通过
      12
      上传者