随机算法+套路思维

第一次遇到随机算法
也不能说没有像那个方向去想

因为我们有n个移动方案
然后组合一共有个所以，对于一个点大概室友的概率被抓到

然后我们就可以靠这个随机枚举个点，然后判断是否可以抓到

就好了。。。。。

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
const int max_n = 1e5+100;
typedef pair<int,int> pii;
pii G[max_n];
int n;

bool check(int x0,int y0,int x1,int y1)
{
    for (int i=1;i<=n;++i)
    {
        int x = x0+G[i].first;
        int y = y0+G[i].second;
        if (x<=0||x>n||y<=0||y>n)continue;
        if ((x==x1&&y==y1)||binary_search(G+1,G+1+n,pii(x1-x,y1-y)))
            return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    int x0,y0,x1,y1;
    cin>>x0>>y0>>x1>>y1;
    for (int i=1;i<=n;++i)cin>>G[i].first>>G[i].second;
    sort(G+1,G+1+n);
    if (check(x0,y0,x1,y1))
    {
        cout<<"Alice wins"<<endl;
        return 0;
    }
    srand(time(NULL));

    int t = 30;
    while (t--)
    {
        int x = rand()%n+1;
        int y = rand()%n+1;
        if (x==x1&&y==y1)
        {
            ++t;
            continue;
        }
        if (!check(x1,y1,x,y))
        {
            cout<<"tie "<<x<<" "<<y<<endl;
            return 0;
        }
    }
    cout<<"Bob wins"<<endl;
}