首页 > 代码库 > 洛谷P1378 油滴扩展
洛谷P1378 油滴扩展
题目:https://www.luogu.org/problem/show?pid=1378
因为n<=6,所以只需要暴力枚举每一种排列即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #define pi 3.1415926535897932384 6 using namespace std; 7 8 int n; 9 double x,y,x2,y2; //x,y left up x1,y1 right down 10 double xx[10],yy[10]; 11 double ans=0; 12 13 int vis[10]; 14 double nx[10],ny[10],nr[10]; 15 16 void dfs(int step,double s){ 17 if (step==n+1){ 18 ans=max(ans,s); 19 return; 20 } 21 for (int i=1;i<=n;++i) 22 if (!vis[i]){ 23 vis[i]=1; 24 nx[step]=xx[i],ny[step]=yy[i]; 25 nr[step]=min(min(x2-nx[step],nx[step]-x),min(y2-ny[step],ny[step]-y)); 26 //cout<<nr[i]<<endl; 27 for (int j=1;j<=step-1;++j){ 28 nr[step]=min(nr[step],sqrt((nx[step]-nx[j])*(nx[step]-nx[j])+(ny[step]-ny[j])*(ny[step]-ny[j]))-nr[j]); 29 if (nr[step]<=0){ 30 nr[step]=0; 31 break; 32 } 33 } 34 dfs(step+1,s+pi*nr[step]*nr[step]); 35 vis[i]=0; 36 } 37 } 38 39 int main(){ 40 scanf("%d",&n); 41 scanf("%lf%lf%lf%lf",&x,&y,&x2,&y2); 42 if (x>x2) swap(x,x2); 43 if (y>y2) swap(y,y2); 44 for (int i=1;i<=n;++i){ 45 scanf("%lf%lf",&xx[i],&yy[i]); 46 } 47 dfs(1,0); 48 printf("%.0lf",(x2-x)*(y2-y)-ans); 49 return 0; 50 }
洛谷P1378 油滴扩展
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。