首页 > 代码库 > 1378 油滴扩展
1378 油滴扩展
难度:普及+/提高
题目类型:搜索
提交次数:2
涉及知识:深搜
题目描述
在一个长方形框子里,最多有N(0≤N≤6)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴,才能使放置完毕后所有油滴占据的总体积最大呢?(不同的油滴不会相互融合)
注:圆的面积公式V=pi*r*r,其中r为圆的半径。
输入输出格式
输入格式:
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标,x,y,x’,y’。
接下去N行,每行两个整数xi,yi,表示盒子的N个点的坐标。
以上所有的数据都在[-1000,1000]内。
输出格式:
一行,一个整数,长方形盒子剩余的最小空间(结果四舍五入输出)
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const double pi = 3.1415926535; 7 const double maxx = 1<<20; 8 int N;//N个点 9 double x1, y11,x2, y2;//对角线坐标 10 double ans, sum; 11 struct point{ 12 int x, y; 13 }p[10]; 14 bool visited[10]; 15 int order[10]; //需要一个存顺序的数组 16 double r[10]; //半径 17 18 double dis(point a, point b){ 19 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 20 } 21 double calculate(int i){ 22 double ans = maxx; 23 double a1 = min(abs(p[i].x-x1), abs(p[i].x-x2)); 24 double a2 = min(abs(p[i].y-y11), abs(p[i].y-y2));//算距离边缘的距离 25 double a = min(a1, a2);//距离边缘的最小距离 26 double b = maxx;//根据其他点算出的最小半径 27 int flag = 0; 28 while(1){ 29 if(order[flag]==i) break; 30 double d = dis(p[order[flag]], p[i]); 31 b = min(d-r[order[flag]], b); 32 flag = order[flag]; 33 } 34 ans = min(a, b); 35 if(ans<0) ans = 0; 36 return ans; 37 } 38 void dfs(int m, int step){//放m号油滴 39 if(step == N+1){ 40 ans = max(sum, ans); 41 return; 42 } 43 else{ 44 for(int i = 1; i <= N; i++){ 45 if(!visited[i]){ 46 visited[i] = true; 47 order[m] = i; //链表,m的下一个存i 48 r[i] = calculate(i); //计算i能达到的半径 49 sum += pi*r[i]*r[i]; 50 dfs(i, step+1); 51 visited[i] = false; 52 sum -= pi*r[i]*r[i]; 53 r[i] = 0; 54 } 55 } 56 } 57 } 58 int main(){ 59 cin>>N; 60 cin>>x1>>y11>>x2>>y2; 61 int i, j; 62 for(i = 1; i <= N; i++) 63 cin>>p[i].x>>p[i].y; 64 double length = abs(x1-x2); 65 double width = abs(y11-y2); 66 dfs(0, 1); 67 cout<<(int)(length*width-ans+0.5); 68 return 0; 69 }
备注:
欢呼~!!!!
历时一个小时,基本上是按照自己的构思独立写完的,第一次提交心里特没底,心想别爆0就好,结果得了70分!于是松了口气,因为知道那30分丢在哪(当r<0即一点被包含时,令r=0,标黄那行)。。然后回去一改,就过了!哈哈哈
写这道题就是为了强化一下自己的搜索。被逼无奈的时候怎么着也能写个暴力骗点分。这道题就是一个赤裸裸的搜索。中间也参考了一下别人的思路,比如那个链表。。当时没有想出来怎么存已放好油滴的顺序(现在想想直接用step做下标就好,不过step是我后加的),最开始dfs的参数就是一个m。不过现在看来m这个参数似乎没啥必要诶。。一个step就够了。
思路就是爆搜,对于每一个点和它放的顺序算出最小半径。(calculate函数要干的事)
要注意的细节还是挺多的。没忘了变量都得用double,表扬自己一下。要先把程序结构想清楚。这次我写代码的顺序是:主函数,dfs,calculate,这样比较有逻辑。
我觉得链表那块我处理的好巧妙啊哈哈哈。
开始的时候把r[i]=0放到sum-=xxx前面了,还奇怪为啥sum不减少orz。
y1这个变量真谜,好像跟什么重名了。。怪不得看到的某题解变量设了个y250……
四舍五入的技巧:(int)(xxx+0.5),好神奇。
总之,做完这道题还是很有成就感很开心的!
1378 油滴扩展