Game【博弈论】-2020杭电多校7

题意

在二维平面上给出 (n) 个点的坐标，初始时刻，有一颗石头在第一个点，两个人轮流移动石头，要求当前移动的距离要比上一次的移动距离大，并且一个点只能用一次。不能移动的人输。问先手胜还是后手胜。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6850

分析

本题关键在于如何确定必胜的策略，可以发现，当一个人选择的是最长边的一个端点，那么另一个人只要选择另一个端点，就可以获胜。如果把最长边依次选取出来，如果最后只剩下起点 (1) 一个点，那么不管先手选择哪一个点，后手总可以选择该点所在边的另一个点，使得先手输，否则先手必胜。

代码

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=2005;
int x[N],y[N];
struct node
{
    ll dis;
    int a,b;
    bool operator < (const node d)const
    {
        return dis>d.dis;
    }
};
vector<node>point;
set<int>st;
bool vis[N];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        point.clear();
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&x[i],&y[i]);
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                ll d=1LL*(x[i]-x[j])*(x[i]-x[j])+1LL*(y[i]-y[j])*(y[i]-y[j]);
                point.pb(node{d,i,j});
            }
        }
        sort(point.begin(),point.end());
        int f=0,sum=n;
        for(int i=0;i<point.size();i++)
        {
            if(vis[point[i].a]||vis[point[i].b]) continue;
            ll td=point[i].dis;
            st.clear();
            int j=i;
            while(j<point.size()&&point[j].dis==td)
            {
                if(vis[point[j].a]||vis[point[j].b])
                {
                    j++;
                    continue;
                }
                st.insert(point[j].a);
                st.insert(point[j].b);
                j++;
            }
            i=j-1;
            set<int>::iterator it;
            for(it=st.begin();it!=st.end();it++)
                vis[*it]=1;
            if(vis[1]&&sum>1)
            {
                f=1;
                break;
            }
            sum-=st.size();
        }
        if(f) printf("YES
");
        else printf("NO
");
    }
    return 0;
}