UVALive 6955 Finding Lines（随机化优化）题解

题意：问你是否有一条直线满足这条直线上的点个数与总个数之比不小于p

思路：解法太暴力了，直接随机取两个数，如果能满足条件就输出可以，否则不行。证明一下为什么可以随机化，题目给出可能有P >=20的点在线上，假设最惨的情况P = 20，有100个点，所以我们选一次选不到这条直线的概率为 1 - (20 * 19) / (100 * 99)，简单点我们记做0.96，那么两次我们找不到这条线的概率为0.96*0.96……，所以我们随机300次（之前随机100次几率0.1都被撞到了），这样选不到这条线的概率就很小很小了，除非RP不行啊。

代码：

#include<ctime>

#include<cmath>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn =  + ;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

struct node{

    int x, y;

}p[maxn];

bool judge(int u, int v,int i){

    int x1 = p[u].x - p[i].x, x2 = p[v].x - p[i].x;

    int y1 = p[u].y - p[i].y, y2 = p[v].y - p[i].y;

    return y1 * x2 == y2 * x1;

}

int main(){

    int n, per;

    while(~scanf("%d%d", &n, &per)){

        per = (int)ceil((double)per /  * n);

        for(int i = ; i < n; i++){

            scanf("%d%d", &p[i].x, &p[i].y);

        }

        if(n <= ){

            printf("possible\n");

            continue;

        }

        srand(time());

        int Time = ;

        bool flag = false;

        while(Time <= ){

            int cnt = ;

            int u = rand() % n;

            int v = rand() % n;

            while(v == u) v = rand() % n;

            for(int i = ; i < n; i++){

                if(i == v || i == u) continue;

                if(judge(u, v, i)) cnt++;

                if(cnt >= per){

                    flag = true;

                    break;

                }

            }

            if(flag) break;

            Time++;

        }

        if(flag)

            printf("possible\n");

        else

            printf("impossible\n");

    }

    return ;

}

巴特西

UVALive 6955 Finding Lines（随机化优化）题解

最新文章

热门文章