40分求调
查看原帖
40分求调
1069315
hm114514楼主2024/8/26 16:01
#include <iostream>
#include <cmath>

using namespace std;

int n;
const int N = 7;
struct {
    int x;
    int y;
    double r;
    bool flow;
} point[N];
int x1, x2, y11, y2;
bool st[N];
int path[N];
double ans = 1145141010;
const double PI = 3.1415926;


void cul() {
    for (int i = 0; i < n; i++) {
        point[i].flow = false;
    }
    for (int i = 0; i < n; i++) {
        int now = path[i];
        double R = 114514;
        for (int j = 0; j < n; j++) {
            if (point[j].flow) {
                int dis = (point[now].x - point[j].x) * (point[now].x - point[j].x) +
                          (point[now].y - point[j].y) * (point[now].y - point[j].y);
                if (dis <= point[j].r * point[j].r) {
                    R = 0;
                }else {
                    R = sqrt(dis) - point[j].r;
                }
            }
        }
        R = min(R, (double) abs(x1 - point[now].x));
        R = min(R, (double) abs(x2 - point[now].x));
        R = min(R, (double) abs(y11 - point[now].y));
        R = min(R, (double) abs(y2 - point[now].y));
        point[now].r = R;
        point[now].flow = true;
    }
    double res = abs((x1 - x2) * (y11 - y2));
    for (int i = 0; i < n; i++) {
        res -= PI * point[i].r * point[i].r;
    }
    ans = min(ans, res);
    cout << ans  << ' ' << res << ' ';
    for(int i = 0;i < n;i++)cout << path[i] << ' ';
    cout << endl;
}

void dfs(int u) {
    if (u == n) {
        cul();
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;
    cin >> x1 >> y11 >> x2 >> y2;
    for (int i = 0; i < n; i++) {
        cin >> point[i].x >> point[i].y;
    }
    dfs(0);
    cout << (int) (ans + 0.5);
}
2024/8/26 16:01
加载中...