暴力排列 40 pts 求调. (精度问题)
查看原帖
暴力排列 40 pts 求调. (精度问题)
609249
Walter_Fang楼主2024/7/5 20:46

基本思想:采用 next_permutation 枚举所有可能的排列,对于每种情况再用 O(n2)O(n^2) 的循环暴力求油滴所覆盖的面积和.

问题:精度存在误差,对于题目所给样例,程序输出 49,得分 40pts40pts.

record.

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=7;
const double inf=2e9,pi=3.1415926535;
struct Node{double x,y;}a[N];
int n,i,ans=inf,p[N];
double x,y,_x,_y,U,D,L,R,S,ro[N];
double dis(Node x,Node y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
double _(){
	int i,j;double u,d,l,r,_r,s=0;
	for(i=1;i<=n;i++){
		auto x=a[p[i]];u=x.x-U;d=D-x.x;l=x.y-L;r=R-x.y;
		_r=inf;
		for(j=i-1;j;j--)_r=min(_r,dis(a[p[i]],a[p[j]])-ro[j]);
		ro[i]=min(u,min(d,min(l,min(r,max(_r,0.0)))));
		s+=ro[i]*ro[i]*pi;
	}
	return s;
}
int main(){
	cin>>n>>x>>y>>_x>>_y;
	U=min(x,_x);D=max(x,_x);L=min(y,_y);R=max(y,_y);S=(D-U)*(R-L);
	for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y,p[i]=i;
	while((p+1,p+1+n))ans=min(ans,(int)(S-_()));
	cout<<ans;
}
2024/7/5 20:46
加载中...