社区讨论

0分求调

P1378油滴扩展参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@losos2y5
此快照首次捕获于
2023/11/10 22:01
2 年前
此快照最后确认于
2023/11/11 08:54
2 年前
查看原帖
CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10e6 + 45;
const int pi = 3.14159265;
int xa, ya, xb, yb, n;
double ans;
bool fl[maxn];
struct node{
    int x, y;
    double r;
}e[maxn];

void dfs (int i, double sum)
{
    if (i == n + 1) ans = max (ans, sum);
    for (int j = 1; j <= n; j ++)
    {
        if (!fl[j])
        {
            int f = 0;
            for (int k = 1; k <= n; k ++)
            {
                if (fl[k] == false && e[j].r >= sqrt((e[j].x - e[k].x) * (e[j].x - e[k].x) + (e[j].y - e[k].y) * (e[j].y - e[k].y) ))
                {
                    fl[j] = true;
                    f = 1;
                    dfs (i + 1, sum);
                    f = 0;
                }
                 
            }
            if (f == 1) continue;
                fl[i] = true;
                e[j].r = min (abs(e[j].x - xa), abs(e[j].x - xb));
                double minn = min (abs(e[j].y - ya), abs(e[j].y - yb));
                e[j].r = min (e[i].r, minn);
                for (int k = 1; k <= n; k ++)
                {
                    if (j != k && fl[k])
                    {
                        double dd = sqrt ((e[j].x - e[k].x) * (e[j].x - e[k].x) + (e[j].y - e[k].y) * (e[j].y - e[k].y) );
                        e[j].r = min (e[j].r, dd - e[j].r);
                    }
                }
                dfs (i + 1, sum + pi * e[j].r * e[j].r);
                e[j].r = 0;
                fl[j] = false;
        }
    }   
}

int main()
{
    cin >> n;
    cin >> xa >> ya >> xb   >> yb;
    xa += 1000, xb += 1000, ya += 1000, yb += 1000;
    for (int i = 1; i <= n; i ++)
    {
        int a, b;
        cin >> a >> b;
        e[i].x = a + 1000;
        e[i].y = b + 1000;
    }
    double ss = abs(xa - xb) * abs(ya - yb);
    dfs (1, 0.0);
    cout << floor(ss - ans - 1) ;
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...