题解 P1378 【油滴扩展】

jins3599 · 2019-10-31 11:37:03 · 题解

很水的搜索...就是半径忘了开double导致我交了很多次（

搜索每一个点，然后枚举所有选过的点，判断当前可以扩展的半径最小值。

（如果当前点被覆盖的话，把r赋值为零）。

然后统计答案即可，最后输出S-ans即可

（我忘记四舍五入居然A了...数据太水了）

复杂度O(2^n*n^2)，n很小，跑的还蛮快的。

#include <bits/stdc++.h>

using namespace std;

const double PI = 3.1415926535;

struct Node {
    double x , y , r;
}a[100];

bool vis[100];
int n;
double ans = 0; 
int maxx , maxy, minx,  miny;

double dis(double x1 , double y1 , double x2 , double y2) {
    return sqrt((x1 - x2)  * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double _min(double a , double b) {
    return a < b ? a : b;
}

void dfs( double sum , int tot) {
    if(sum > ans) ans = sum;

    if(tot >= n) return;

    for(int i = 1 ; i <= n ; ++ i) {
        if(vis[i]) continue;
        double r ;
        r = _min(maxx - a[i].x , a[i].x - minx);
        r = _min(r , _min(maxy - a[i].y , a[i].y - miny));
        bool flag = 0;
        for(int j = 1 ; j <= n ; ++ j) {
            if(vis[j]) {
                if(dis(a[j].x , a[j].y , a[i].x , a[i].y) <= a[j].r) {
                    flag = 1; break;
                }
            }
            if(vis[j]) r = _min(r , dis(a[j].x , a[j].y , a[i].x , a[i].y) - a[j].r);
        } 
        if(flag) r = 0.0;
        vis[i] = 1;
        a[i].r = r;
        dfs(sum + PI * r * r , tot + 1);
        vis[i] = 0;
    }
} 

int main () {
    scanf("%d" , &n);
    scanf("%d%d%d%d" , &maxx , &maxy , &minx , & miny);
    if(minx > maxx) swap(maxx , minx);
    if(miny > maxy) swap(miny , maxy);
    double S = (double)((maxx - minx) * (maxy - miny)); 
    for(int i = 1 ; i <= n; ++ i) scanf("%lf%lf" , &a[i].x , &a[i].y);  
    dfs(0 , 0);
    printf("%.0lf\n" , (S - ans) + 0.5);
    return 0;
}