1076. [NOIP2010冲刺六] 油滴扩展

 1 #include<cmath>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 int n,xa,ya,xb,yb;
 7 const double infd=100000000.0;//这个是对于double的INF 
 8 const double PI=acos(-1);//为了精度 
 9 double ans;
10 int x[10],y[10];
11 double r[10];
12 int seq[10];
13 int fact[10]={0,1,2,6,24,120,720};//阶乘值,其实就是全排列数 
14 double dist(int a,int b){//求两圆a,b的圆心距 
15     return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
16 }
17 void solve(){
18     double cur;//current answer目前的答案 
19     cur=abs(xa-xb)*abs(ya-yb);//刚开始还没被油滴覆盖,所以是整个盒子面积 
20     for(int i=0;i<n;i++){//对填充序列中的每个圆计算其在此情况下的半径 
21         double mr=infd;//当前圆的半径的最大值max radian(mr) 
22         mr=min(min(abs(x[seq[i]]-xa),abs(x[seq[i]]-xb)),min(abs(y[seq[i]]-ya),abs(y[seq[i]]-yb)));
23         //以上该行只考虑了盒子边界，未考虑其他之前填好的圆 
24         for(int j=0;j<i;j++){//现在考察之前扩展完毕的油滴 
25             double t=dist(seq[i],seq[j])-r[seq[j]];
26             //圆心距减去该圆半径，有可能有负数，此时本圆被包含在之前的圆中，需要特判，否则WA,60分 
27             mr=mr<max(t,(double)0)?mr:max(t,(double)0);//特判。三思而后提交！consider twice before you submit!
28         }
29         r[seq[i]]=mr;//记录该圆半径 
30         cur-=PI*mr*mr;//计算目前未被覆盖的面积 
31     }
32     ans=min(ans,cur);//更新答案 
33     return;
34 }
35 int main(){
36     freopen("oilbox.in","r",stdin);
37     freopen("oilbox.out","w",stdout);
38     cin>>n>>xa>>ya>>xb>>yb;
39     ans=abs(xa-xb)*abs(ya-yb);//初始化 
40     for(int i=0;i<n;i++){
41         seq[i]=i;
42         cin>>x[i]>>y[i];
43     }
44     for(int i=0;i<fact[n];i++){
45         solve();
46         next_permutation(seq,seq+n);//求下一个排列 
47     }
48     printf("%.0lf",ans);
49     return 0;
50 }