首页 > 代码库 > 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 油滴扩展