在比赛时我嫌麻烦,最后一问随便判了个奇偶性,结果怎么过了?
#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;
}