0分求助
查看原帖
0分求助
358605
狼群夜空楼主2022/9/6 20:59

本篛笱没有查出来问题出在哪里了,求大佬帮助

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std ;
inline int IN()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f*x;
}

const int N = 10 , M = 1000 ;
const double pi = 3.1415926 ;

inline double count(double xx , double xxx , double yy , double yyy){return sqrt((xxx - xx) * (xxx - xx) + (yyy - yy) * (yyy - yy)) ;}
inline double Max(double a , double b){return a > b ? a : b ;}
inline double Min(double a , double b){return a < b ? a : b ;}
inline double Abs(double a , double b){return a > b ? (a - b) : (b - a) ;}

int n , xx1 , xx2 , yy1 , yy2 ;
int x[N] , y[N] ;
double ans , r[N] ;
bool vis[N] ;

void dfs(int num , double sum)
{
	if(num == n + 1) {ans = Max(ans , sum) ; return ;} // 都搜完了,更新答案 
	for(int i = 1 ; i <= n ; i ++ )
	{
		if(vis[i]) continue ;
		bool is = 0 ; // 判断当前点是否在其他点里 
		for(int j = 1 ; j <= n ; j ++ ) // 遍历其他所有点 
		{
			if(vis[j] && r[j] >= count(x[i] , x[j] , y[i] , y[j])) // 如果 j 点遍历过且包含 i 点 
			{
				is = 1 ; // i 点在其他点里 
				vis[i] = 1 ; // 因为在其他点里,所以不用遍历了,标记为 true 
				dfs(num + 1 , sum) ; //搜索下一个点 
				vis[i] = 0 ; // 回溯 
			}
		}	
		if(is == 1) continue ;
		vis[i] = 1 ;
		r[i] = Min(Abs(x[i] , xx1) , Abs(x[i] , xx2)) ;
        r[i] = Min(r[i] , Min(Abs(y[i] , yy1) , Abs(y[i] , yy2))) ; //此油滴的可能半径为到边界的最短路径 
		for(int j = 1 ; j <= n ; j ++ ) //根据已经扩展的油滴(j)半径来确定 此油滴(i)的最小半径 
		{
			if(i != j && vis[j]) // 如果不是同一个点且已访问过 
			{
				double d = count(x[i] , x[j] , y[i] , y[j]) ;
				r[i] = Min(r[i] , d - r[j]) ;
			}
		}
		dfs(num + 1 , sum + pi * r[i] * r[i]) ; // 寻找下一个油滴 
		r[i] = 0 ; vis[i] = 0 ; // 回溯 
	}
}

int main()
{
	n = IN() ; xx1 = IN() + M ; xx2 = IN() + M ; yy1 = IN() + M ; yy2 = IN() + M ;
	for(int i = 1 ; i <= n ; i ++ ) 
		x[i] = IN() + M , y[i] = IN() + M ; // 加 1000 避免负数 
	dfs(1 , 0.0) ; 
	ans = Abs(xx1 , xx2) * Abs(yy1 , yy2) - ans ;
	int answer=int(ans+0.5); // 四舍五入 
	    printf("%d",answer);
	return 0 ;
}
2022/9/6 20:59
加载中...