萌新求助格式错误
查看原帖
萌新求助格式错误
677234
FstAutoMaton楼主2024/1/29 13:27

RT,交在 vjudge 上显示 PE 了,但感觉输出格式没错啊???

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

using namespace std;
#define double long double
#define LL long long;

const int kMaxN = 16;

double x[kMaxN], y[kMaxN], v[kMaxN], l[kMaxN], q[kMaxN], px, ans;
int vis[kMaxN], id[kMaxN], n;
vector<int> t;

double M(int a, int b, int c) {
  return (x[b] - x[a]) * (y[c] - y[a]) - (x[c] - x[a]) * (y[b] - y[a]);
}

double D(int l, int r) {
  return sqrt((x[r] - x[l]) * (x[r] - x[l]) + (y[r] - y[l]) * (y[r] - y[l]));
}

bool C(int x, int y) {
  double v = M(0, x, y);
  return v > 0 || !v && D(x, 0) < D(y, 0);
}

void D(int s, double sum, double len) {
  if (s > n) {
    int cnt = 0, r = 0;
    double lx = 0;
    x[0] = y[0] = 1e9;
    for (int i = 1; i <= n; i++) {
      if (!vis[i]) {
        id[++cnt] = i;
        if (x[i] < x[0]) {
          x[0] = x[i], y[0] = y[i];
        } else if (x[i] == x[0]) {
          y[0] = min(y[0], y[i]);
        }
      }
    }
    sort(id + 1, id + cnt + 1, C);
    for (int i = 1; i <= cnt; i++) {
      for (; r > 1 && M(q[r - 1], q[r], id[i]) <= 0; r--) {
      }
      q[++r] = id[i];
    }
    for (int i = 1; i < r; i++) {
      lx += D(q[i], q[i + 1]);
    }
    lx += D(q[1], q[r]);
    if (lx <= len) {
      if (sum > ans) {
        ans = sum;
        t.clear();
        px = 0;
        for (int i = 1; i <= n; i++) {
          if (vis[i]) {
            t.push_back(i);
          }
        }
        px = len - lx;
      }
    }
    return;
  }
  D(s + 1, sum + v[s], len);
  vis[s] = 1;
  D(s + 1, sum, len + l[s]);
  vis[s] = 0;
}

void I() {
  t.clear();
  for (int i = 1; i <= n; i++) {
    x[i] = y[i] = v[i] = l[i] = q[i] = vis[i] = id[i] = 0;
  }
  px = ans = 0;
}

int main() {
  // freopen(".out", "w", stdout);
  int c = 0;
  while (cin >> n) {
    if (!n) {
      return 0;
    }
    if (c) {
      cout << "\n";
    }
    c++;
    for (int i = 1; i <= n; i++) {
      cin >> x[i] >> y[i] >> v[i] >> l[i];
    }
    D(1, 0, 0);
    cout << "Forest " << c << "\n";
    cout << "Cut these trees:";
    for (int i = 0; i < t.size(); i++) {
      cout << " " << t[i];
    }
    cout << "\n";
    cout << "Extra wood: ";
    printf("%.2Lf", px);
    I();
  }
  return 0;
}
2024/1/29 13:27
加载中...