求条
查看原帖
求条
935314
xplor楼主2024/10/23 13:43
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 10005;
struct node {
	int x;
	int y;
} a[N];
LL n;
LL dis[N][N];
LL sum;
vector<LL> e[N];
LL dep[N];
bool tmp;
//bool flag[N][N];
void dfs (LL u, LL fa) {
	dep[u] = dep[fa] + 1;
	for (LL i = 0; i < e[u].size (); i ++ ) {
		LL v = e[u][i];
		if (v == fa) continue;
		dfs (v, u);
	}
}
LL dp[N];
LL diss (LL i, LL j) {
	return (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);	
}
int main () {
//	freopen ("war.in", "r", stdin);
//	freopen ("war.out", "w", stdout);
	scanf ("%lld", &n);
	for (LL i = 1; i <= n; i ++ ) {
		LL x, y;
		scanf ("%lld%lld", &a[i].x, &a[i].y);
//		diss[i][0] = abs(a[i].x) * abs(a[i].x) + abs(a[i].y) * abs(a[i].y);
//		diss[0][i] = abs(a[i].x) * abs(a[i].x) + abs(a[i].y) * abs(a[i].y);
	}
//	for (LL i = 1; i <= n; i ++ ) {
//		for (LL j = 1; j <= n; j ++ ) {
//			if (i == j) continue;
//			diss[i][j] = abs (a[i].x - a[j].x) * abs (a[i].x - a[j].x) + abs (a[i].y - a[j].y) * abs (a[i].y - a[j].y);
//		}
//	}
	for (LL i = 1; i <= n; i ++ ) {
		LL minn = 1e18;
		LL id;
		for (LL j = 0; j <= n; j ++ ) {
			if (i == j) continue;
			if (diss (j, 0) <= diss (i, 0) && diss (i, j) < minn) {
				minn = diss (i, j);
				id = j;
			}
		}

			e[i].push_back (id);
			e[id].push_back (i);

	}
	dfs (0, -1);
	for (LL i = 0; i <= n; i ++ ) {
		sum += dep[i];
	}
	if (sum % 2) {
		puts ("No");
		return 0;	
	}
	sum /= 2;
	for (LL i = 1; i <= sum; i ++ ){
		for (LL j = 1; j <= n; j ++ ){
			if (i - dep[j] > 0) dp[i] += dp[i - dep[j]];
			if (i - dep[j] == 0) dp[i] ++; 
		}
	}
	if (dp[sum]) puts ("Yes");
	else puts ("No");
	return 0;
}

here

2024/10/23 13:43
加载中...