建议加强数据
查看原帖
建议加强数据
895690
gghack_Nythix楼主2024/5/26 18:52

在比赛时我嫌麻烦,最后一问随便判了个奇偶性,结果怎么过了?

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
struct data{
	int x,y;
}a[600];
double dist(int i,int j){
	double x = a[i].x,y = a[i].y;
	double xx = a[j].x,yy = a[j].y;
	return ((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
vector<int>g[2005];
int dis[605];
bool vis[605];
void bfs(int x) {
	queue<int>q;
	q.push(x);
	vis[x] = 1;
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		for(auto x : g[now]) {
			if(!vis[x]) {
				dis[x] = dis[now] + 1;
				vis[x] = 1;
				q.push(x);
			}
		}
	}
	return ;
}
int dp[20005];
signed main(){
	int n;
	cin >> n;
	a[0].x = a[0].y = 0;
	for(int i = 1;i <= n;++i) cin >> a[i].x >> a[i].y;
	for(int i = 1;i <= n;++i) {
		int pos = 0;
		for(int j = 0;j <= n;++j) if(dist(j,0) <= dist(i,0) && dist(i,j) < dist(i,pos) && i != j) pos = j;
		g[i].pb(pos);
		g[pos].pb(i);
	}
	bfs(0);
	int sum = 0;
	for(int i = 0;i <= n;++i) sum += dis[i] + 1;
	if(sum & 1) cout << "No\n";
	else cout << "Yes\n";
	return 0;
}
2024/5/26 18:52
加载中...