P1378-油滴扩展

 1 #include <bits/stdc++.h>
 2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
 3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
 4 #define INF 0x3f3f3f3f
 5 #define PI 3.1415926535
 6 typedef long long ll;
 7 using namespace std;
 8 inline ll read()
 9 {
10     ll ans = 0;
11     char ch = getchar(), last = ‘ ‘;
12     while(!isdigit(ch)) last = ch, ch = getchar();
13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
14     if(last == ‘-‘) ans = -ans;
15     return ans;
16 }
17 inline void write(ll x)
18 {
19     if(x < 0) x = -x, putchar(‘-‘);
20     if(x >= 10) write(x / 10);
21     putchar(x % 10 + ‘0‘);
22 }
23 struct P
24 {
25     double x;
26     double y;
27 };
28 double height[2];
29 double width[2];
30 int vis[8];
31 P point[8];
32 double pointr[8];
33 int N;
34 double rnt = 0;
35 double reach(P p1,P p2)
36 {
37     return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
38 }
39 double findr(int i)
40 {
41     double rnt = 10000;
42 
43     rnt = min(rnt,min(point[i].x-width[0],width[1]-point[i].x));
44     rnt = min(rnt,min(point[i].y-height[0],height[1]-point[i].y));
45     _for(j,0,N)
46     {
47         if(i==j)
48             continue;
49         if(abs(reach(point[i],point[j])<pointr[j]))
50             rnt = 0;
51         if(pointr[j])
52             rnt = min(rnt,abs(reach(point[i],point[j])-pointr[j]));
53     }
54     return rnt;
55 }
56 void dfs(int step,double area)
57 {
58     if(step==N)
59         rnt = max(rnt,area);
60 
61     _for(i,0,N)
62     {
63         if(!vis[i])
64         {
65             double r = findr(i);
66             pointr[i] = r;
67             vis[i] = 1;
68             dfs(step+1,area+PI*r*r);
69             vis[i] = 0;
70             pointr[i] = 0;
71         }
72     }
73 }
74 int main()
75 {
76     N = read();
77     width[0] = read(),height[0] = read(),width[1] = read(),height[1] = read();
78     sort(width,width+2);
79     sort(height,height+2);
80     _for(i,0,N)
81     point[i].x = read(),point[i].y = read();
82     memset(vis,0,sizeof(vis));
83     dfs(0,0);
84 
85     write((width[1]-width[0])*(height[1]-height[0])-(int)(rnt+0.5));
86     return 0;
87 }