80求调
  • 板块P1378 油滴扩展
  • 楼主liujb
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/21 00:23
  • 上次更新2024/9/21 00:23:41
查看原帖
80求调
818698
liujb楼主2024/9/21 00:23

#6 #7 没过

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int n;
int x[N], y[N], e[4];
double rad[N];
int path[N], vis[N];
double ans;
double cal() {
    memset(rad, 0x3f, sizeof rad);
    double res = 0;
    for(int i = 1; i <= n; i ++ ) {
        rad[i] = 1.0 * min(min(abs(x[path[i]] - e[0]), abs(x[path[i]] - e[2])), min(abs(y[path[i]] - e[1]), abs(y[path[i]] - e[3])));
        for(int j = 1; j < i; j ++ ) {
            double d = sqrt((x[path[i]] - x[path[j]]) * (x[path[i]] - x[path[j]]) + (y[path[i]] - y[path[j]]) * (y[path[i]] - y[path[j]])); 
            if(d >= rad[j]) rad[i] = min(rad[i], fabs(d - rad[j]));
            else rad[i] = 0;
        }
        res += rad[i] * rad[i] * M_PI;
        // cout << path[i] << ' ' << rad[i] << endl;
    }
    return res;
}
void dfs(int u) {
    if(u > n) {
        ans = max(cal(), ans);
        return ;
    }
    for(int i = 1; i <= n; i ++ ) {
        if(!vis[i]) {
            vis[i] = 1;
            path[u] = i;
            dfs(u + 1);
            vis[i] = 0;
            path[u] = 0;
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < 4; i ++ ) cin >> e[i];
    for(int i = 1; i <= n; i ++ ) cin >> x[i] >> y[i];
    dfs(1);
    cout << abs(e[0] - e[2]) * abs(e[1] - e[3]) - ans;
    return 0; 
}
2024/9/21 00:23
加载中...