Fruit Ninja(头一次接触的随机化算法)

Fruit Ninja

题意

屏幕上有n个水果，你可以画一条直线切掉其中一些，给你N和x，M/N>=x，M为切掉的水果数，x为0~1的纯小数，指的是切掉的水果比吧。问你是否有满足这个式子的这样一条直线，有输出yes，没有输出no。

N<=1e4 , x小数点后一位（0,1）。

思路

随机化，巧妙巧妙，厉害厉害，佩服佩服，不过要分析一波随机的数量。由于m是切掉的水果数，n是总水果数，x是两者之比，也就是说在这条直线上的水果数是m个，意味着随机选一个水果，刚好在直线上的概率是x，因此随机选两个刚好组成这条直线的概率是x^2，而x∈[0.1,0.9]，因此概率最小为0.01，也就是说取100次就能取到那条我们需要的直线，反之如果没有满足的，就说明“NO”。为了保险起见，我们将随机范围设置为200。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    ll x,y;
};
node point[10010];
int main()
{
    int t;
    srand((unsigned)time(NULL));
    scanf("%d",&t);
    while(t--)
    {
        int n;
        double x;
        scanf("%d%lf",&n,&x);
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&point[i].x,&point[i].y);
        }
        int flag=0;
        for(int i=0;i<200;i++)
        {
            int a=rand()%n;
            int b=rand()%n;
            while(a==b)
                a=rand()%n;

            int cnt=0;
            for(int j=0;j<n;j++)
                if((point[a].x-point[b].x)*(point[a].y-point[j].y)==(point[a].y-point[b].y)*(point[a].x-point[j].x))
                    cnt++;

            if(cnt>=n*x)
            {
                flag=1;break;
            }
        }
        if(flag)    puts("Yes");
        else puts("No");
    }
    return 0;
}