关键字：搜索，模拟。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油 滴不会相互融合）
注：圆的面积公式V=pi*r*r，其中r为圆的半径。
Input Format
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标，x,y,x',y’。
接下去N行，每行两个整数xi,yi，表示盒子的N个点的坐标。
以上所有的数据都在[-1000，1000]内。
Output Format
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。
Sample Input #1
2
20 0 10 10
13 3
17 7
Sample Output #1
50
简单的搜索题，枚举每滴油滴落的顺序，油滴的半径就是与边框相切，或者与其它油滴外切的最小半径。
惟一需要注意的细节是：如果新的油滴中心位于已有的油滴之内，那么新油滴半径为0.
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 | #include <stdio.h>#include <math.h>int n,xa,ya,xb,yb,x[10],y[10];short vis[10];double ans = 0,r[10];int abs(int num){ return num>0?num:-num;}double max(double a, double b){ return a>b?a:b;}double min(double a, double b){ return a<b?a:b;}void dfs(int dep,double tans){ int i,j; if(dep>n) {ans = ans>tans?ans:tans; return;} for(i=1;i<=n;i++) { if(vis[i]) continue; vis[i] = 1; r[i] = min(abs(y[i]-ya),abs(y[i]-yb)); r[i] = min(r[i],min(abs(x[i]-xa),abs(x[i]-xb))); for(j=1;j<=n;j++) { if(i == j || !vis[j]) continue; r[i] = max(0,min(r[i],sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[j])); } dfs(dep+1,tans+3.1415926535*r[i]*r[i]); vis[i] = 0; }}int main(){ int i; scanf("%d%d%d%d%d",&n,&xa,&ya,&xb,&yb); for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); dfs(1,0); printf("%d",(int)(abs(xa-xb)*abs(ya-yb)-ans+0.5)); return 0;} |
评论 (0)
