題目

在一個長方形框子里，最多有N（0≤N≤6）個相異的點，在其中任何一個點上放一個很小的油滴，那么這個油滴會一直擴展，直到接觸到其他油滴或者框子的邊界。必須等一個油滴擴展完畢才能放置下一個油滴。那么應該按照怎樣的順序在這N個點上放置油滴，才能使放置完畢后所有油滴占據的總體積最大呢？（不同的油滴不會相互融合）

注：圓的面積公式V=pirr，其中r為圓的半徑。

分析

用stl自帶的next_permutation 枚舉油滴擴展的順序（最多720種）

每確定一種順序，求一次答案

貪心地將當前點擴展到最大，如果當前點已經被前面的油滴覆蓋到，那么這個點不放油滴 , 畫圖可以感性認識，這種情況最大，不知道怎么證明...

最后輸出答案，四舍五入就是將當前的小數答案+0.5 再向下取整

代碼

#include<bits/stdc++.h>#define For(i,a,b) for(int i=(a); i<=(b) ; i++)#define _For(i,a,b) for(int i=(a); i>=(b) ; i--)#define Memset(a,b); memset((a),(b),sizeof((a)));#define Cout(a,b); printf("%d",(a));printf(b);#define Coutc(a,b); printf("%c",(a));printf(b);#define Couts(a,b); printf("%s",(a));printf(b);using namespace std;const int INF = 0x3f3f3f3f;typedef long long LL;typedef unsigned long long ULL;typedef long double LDB;inline LL CinLL(){LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}inline int Cin(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;}struct cre{double x,y,r,are;bool use;}a[10];const double p = acos(-1);const double eps = 1e-8;double xx1,yy1,xx2,yy2;int n;int sx[] = {0,1,2,3,4,5,6};inline double dis(double xa,double ya,double xb,double yb){return sqrt((xb - xa) * (xb - xa) + (yb - ya ) * (yb - ya));}double solve(){For(i,1,n){int now = sx[i];double rr = 99999999;int flag = 0;For(j,1,i-1)if(dis(a[now].x,a[now].y,a[sx[j]].x,a[sx[j]].y) <= a[sx[j]].r){a[now].use = false;flag = 1;break;}if(flag)continue;For(c,1,i-1){int j= sx[c];if(a[j].use == false) continue;double kk = dis(a[now].x,a[now].y,a[j].x,a[j].y) - a[j].r;rr = rr < kk ? rr : kk;}rr = rr < (a[now].x - xx1) ? rr : (a[now].x - xx1); rr = rr < (xx2 - a[now].x) ? rr : (xx2 - a[now].x);rr = rr < (a[now].y - yy1) ? rr : (a[now].y - yy1);rr = rr < (yy2 - a[now].y) ? rr : (yy2 - a[now].y);a[now].r = rr;a[now].are = p * a[now].r * a[now].r;a[now].use = true;} double sum = 0;For(i,1,n) sum += a[i].are;return sum;}int main(){ios::sync_with_stdio(false);cin>>n;cin>>xx1>>yy1>>xx2>>yy2;if(xx1 > xx2){swap(xx1,xx2);swap(yy1,yy2);}if(yy1 > yy2) swap(yy1,yy2);For(i,1,n) cin>>a[i].x>>a[i].y;double ans = 0;double tim = 1;For(i,2,n) tim*=i;For(i,1,tim){For(j,1,n) {a[j].are = a[j].r = 0;a[j].use = false;}double k = solve();ans = ans > k ? ans : k;next_permutation(sx+1,sx+n+1);}double res = (xx2 - xx1) * (yy2 - yy1) - ans;int ress = (res + 0.5+eps);cout<<ress;}

轉載于:https://www.cnblogs.com/greenty1208/p/8667319.html

總結

以上是生活随笔為你收集整理的【洛谷P1378】油滴扩展的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。