P1378 油滴扩展

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 bool s[7];
 7 double x[7], y[7], r[7], xa, ya, xb, yb, maxs;
 8 int n;
 9 const double PI = 3.1415926535;
10 
11 void dfs(int num, double sum)
12 {
13     if (num > n)
14     {
15         maxs = max(maxs, sum);
16         return;
17     }
18     for (int i = 1; i <= n; i++)
19     {
20         if (!s[i])
21         {
22             double s1 = min(fabs(x[i] - xa), fabs(x[i] - xb));
23             double s2 = min(fabs(y[i] - ya), fabs(y[i] - yb));
24             double mind = min(s1, s2);
25             for (int j = 1; j <= n; j++)
26                 if (i != j && s[j])
27                 {
28                     double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
29                     mind = min(mind, max(d - r[j], 0.0));
30                 }
31             r[i] = mind;
32             s[i] = 1;
33             dfs(num + 1, sum + r[i] * r[i] * PI);
34             s[i] = 0;
35         }
36     }
37 }
38 int main()
39 {
40     double t;
41     cin >> n;
42     cin >> xa >> ya >> xb >> yb;
43     t = fabs(xa - xb) * fabs(ya - yb);
44     for (int i = 1; i <= n; i++)
45         cin >> x[i] >> y[i];
46     dfs(1, 0);
47     cout << int(t - maxs + 0.5);
48 }