洛谷 P1378 油滴扩展

成功达成成就:很有困意的情况下写完了一道搜索题,而且不是一遍写对,是后来又查了错。。
困的情况下也能写出这种稍微有些麻烦的搜索题足见我功力之高(逃
需要注意一下输出时会出现的精度问题,否则WA两个点。
参考:https://www.luogu.org/blog/2002102430204070yl/solution-p1378

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int x01,y01,x02,y02;
struct point{
    int x,y;
    double r;
    bool occupied;
}points[10];
int arr[10];
double dis[10][10];
inline double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double checkR(int p){
    if(points[p].occupied)return 0;
    double r=min(min(abs(y01-points[p].y),abs(y02-points[p].y)),min(abs(x01-points[p].x),abs(x02-points[p].x)));
    for(int i=1;i<=n;i++){
        if(i==p||!points[i].occupied)continue;
        r=min(r,dis[p][i]-points[i].r);
    }
    if(r<0)r=0;
    points[p].r=r;
    points[p].occupied=true;
    for(int i=1;i<=n;i++){
        if(points[i].occupied)continue;
        if(r>=dis[p][i])points[i].occupied=true;
    }
    return r*r*3.1415926;
}
inline double dfs(int pos,double area){
    if(pos==n+1)return area;
    return dfs(pos+1,area+checkR(arr[pos]));
}
int main(){
    cin>>n;
    cin>>x01>>y01>>x02>>y02;
    for(int i=1;i<=n;i++)cin>>points[i].x>>points[i].y;
    for(int i=1;i<=n;i++)arr[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            double v=dist(points[i].x,points[i].y,points[j].x,points[j].y);
            dis[i][j]=dis[j][i]=v;
        }
    }
    double maxV=0;
    do{
        for(int i=1;i<=n;i++){
            points[i].r=0;
            points[i].occupied=false;
        }
        double v=dfs(1,0);
        maxV=max(maxV,v);
    }while(next_permutation(arr+1,arr+n+1));
    long long v=(long long)(abs(x01-x02)*abs(y01-y02)-maxV+0.5);
    cout<<v;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注