dfsTLE求调
查看原帖
dfsTLE求调
1272259
cgxd楼主2024/10/30 22:44
#include<bits/stdc++.h>
using namespace std;
int n, m, fa[8005], dep[8005];
vector<int> G[8005];
void dfs(int u, int la){
	fa[u] = la;
	dep[u] = dep[la] + 1;
	for(int i: G[u]) dfs(i, u);
}struct circle{
	complex<int64_t> o;
	int64_t r;
	//circle(int64_t x, int64_t y, int64_t n):o(complex<int64_t>(x, y)), r(n){}
	bool operator<(const circle &c1)const{
		return r < c1.r;
	}bool cont(complex<int64_t> c){
		c -= o;
		return c.real() * c.real() + c.imag() * c.imag() < r * r;
	}
};
vector<circle> v(1);
signed main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int64_t a, b, r;
		scanf("%lld%lld%lld", &a, &b, &r);
		v.push_back(circle{complex<int64_t>(a, b), r});
	}sort(v.begin() + 1, v.end());
	v.push_back(circle{complex<int64_t>(0, 0), INT_MAX});
	for(int i = 1; i < n; ++i){
		for(int j = i + 1; j <= n; ++j){
			if(v[j].cont(v[i].o)){
				G[j].push_back(i);
				break;
			}
		}
	}dfs(n, 0);
	scanf("%d", &m);
	while(m--){
		int u[2];
		for(int j = 0; j < 2; ++j){
			int64_t a, b;
			scanf("%lld%lld", &a, &b);
			complex<int64_t> co(a, b);
			for(int k = 1; k <= n; ++k){
				if(v[k].cont(co)){
					u[j] = k;
					break;
				}
			}
		}int res = 0;
		while(u[0] != u[1]){
			if(dep[u[0]] > dep[u[1]]) u[0] = fa[u[0]];
			else u[1] = fa[u[1]];
			++res;
		}printf("%d\n", res);
	}return 0;
}
2024/10/30 22:44
加载中...