随机算法 - HNU 13348 Finding Lines

2024-09-05 17:08

本文主要是介绍随机算法 - HNU 13348 Finding Lines,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 Finding Lines

Problem's Link:  http://acm.hnu.cn/online/?action=problem&type=show&id=13348&courseid=0


 

Mean: 

给你平面上1e5个点,让你判断是否可以找到一条直线,使得p%的点都在这条直线上。

analyse:

经典的随机算法题。

每次随机出两个点,然后对n个点进行判断,看是否有p%的点在这条直线上。

关于随机算法正确性的证明:

每次随机一个点,这个点在直线上的概率是p,p最小为20%;

随机两个点来确定一条直线,那么随机一条直线的概率就是p*p,即:4%;

也就是说,在直线上概率为0.04,不在的概率为1-0.04=0.96;

那么随机k次不在直线上的概率为0.96^k,也就是答案出现误差的概率。

这题我们随机1000次,错误的概率接近1e-18,基本是不可能事件,证毕.

Time complexity: O()

 

Source code: 

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-02-17.06
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#define  LL long long
#define  ULL unsigned long long
using namespace std;
const LL MAXN = 100010;

LL n , p;
LL x [ MAXN ], y [ MAXN ];
int main()
{
      srand( time( NULL ) );
      while( ~ scanf( "%lld %lld" , &n , &p ) )
      {
            for( LL i = 0; i < n; ++ i )
                  scanf( "%lld %lld" , & x [ i ], & y [ i ] );
            if( n == 1 ) { puts( "possible" ); continue; }
            LL sum = 0;
            if( n * p % 100 == 0 ) sum = n * p / 100;
            else sum = n * p / 100 + 1;
            LL T = 1000;
            bool flag = false;
            while( T -- )
            {
                  LL a = ( LL ) rand() * ( LL ) rand() % n;
                  LL b = ( LL ) rand() * ( LL ) rand() % n;
                  if( a == b ) continue;
                  LL num = 2;
                  for( LL j = 0; j < n; ++ j )
                  {
                        if( j == a || j == b ) continue;
                        if( ( y [ j ] - y [ a ] ) * ( x [b ] - x [ a ] ) == ( x [ j ] - x [ a ] ) * ( y [b ] - y [ a ] ) ) num ++;
                  }
                  if( num >= sum ) { flag = true; break ;}
            }
            if( flag ) puts( "possible" );
            else puts( "impossible" );
      }
      return 0;
}
/*

*/

 

 另外一种据说更高效的解法:

// Time complexity: O(n/(p/100)^2)
// Memory: O(n)

/* Solution method:
*
* Select 10000 (or more) pairs of points at random, and determine the lines that go through them.
* If 20% (or more) of all points are on the same line, we expect to find it about 400 times(*).
* For all lines that we find more than 230 times (at most 43), see how many points are on it.
* Report "possible" if one of them works.
* (*) Worst case: 15 points, p=20%, exactly 3 on one line: E = 10000/35 = 285.7, sigma = 16.7
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
using namespace std;

const int N = 1000000;
const int samples = 10000 , threshold = 230;

int X [N ], Y [N ];

int gcd ( int a , int b)
{     return b ? gcd(b , a %b) : a;
}

struct line
{     long long a , b , c; // ax+by=c
    line() {}
    // Construct line through (x1,y1) and (x2,y2)
    line ( int x1 , int y1 , int x2 , int y2)
    {     int d = gcd( abs( x1 - x2 ), abs( y1 - y2));
        if ( x1 - x2 < 0)
            d = - d;
        a = -( y1 - y2) / d;
       b = ( x1 - x2) / d;
        c = a * x1 + b * y1;
    }
};

bool operator < ( line L1 , line L2)
{     return L1 . a < L2 . a || ( L1 . a == L2 . a && ( L1 .b < L2 .b || ( L1 .b == L2 .b && L1 . c < L2 . c)));
}

map < line , int > Cnt;

// RNG (modulo 2^32)
unsigned int randnr()
{     static unsigned int rseed = 131;
    return rseed = 22695477 * rseed + 1;
}

int main()
{     int n , p , i , j , m , s;
    long long a , b , c;
    map < line , int >:: iterator it;
    // Read input
    scanf( "%d %d" , &n , &p);
    for ( i = 0; i < n; i ++)
        scanf( "%d %d" , & X [ i ], & Y [ i ]);
    // Special case: n=1
    if (n == 1)
    {     printf( "possible \n ");
        return 0;
    }
    // Try a lot of random pairs of points
    for (s = 0; s < samples; s ++)
    {
            i = randnr() % n;
        do
            j = randnr() % n;
        while ( j == i);
        Cnt [ line( X [ i ], Y [ i ], X [ j ], Y [ j ])] ++; // Add to count
    }
    // Check all lines whose count is above the threshold
    for ( it = Cnt . begin(); it != Cnt . end(); it ++)
        if ( it -> second > threshold)
        {     a = ( it -> first ). a;
           b = ( it -> first ).b;
            c = ( it -> first ). c;
            m = 0; // Count
            for ( i = 0; i < n; i ++)
                if ( a * X [ i ] + b * Y [ i ] == c)
                    m ++;
            if ( 100 * m >= n *p)
            {     printf( "possible \n ");
                return 0;
            }
        }
    printf( "impossible \n ");
    return 0;
}

 再附上一种二分的做法:

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;

const int N = 1000000;

int X [N ], Y [N ];

int gcd ( int a , int b)
{     return b ? gcd(b , a %b) : a;
}

struct line
{     long long a , b , c; // ax+by=c
    line() {}
    // Construct line through (x1,y1) and (x2,y2)
    line ( int x1 , int y1 , int x2 , int y2)
    {     int d = gcd( abs( x1 - x2 ), abs( y1 - y2));
        if ( x1 - x2 < 0)
            d = - d;
        a = -( y1 - y2) / d;
       b = ( x1 - x2) / d;
        c = a * x1 + b * y1;
    }
};

bool operator < ( line L1 , line L2)
{     return L1 . a < L2 . a || ( L1 . a == L2 . a && ( L1 .b < L2 .b || ( L1 .b == L2 .b && L1 . c < L2 . c)));
}

set < line > findlines ( int first , int last , int p)
{     int mid = ( first + last) / 2;
    int a , b , c , i , j , m;
    set < line > S , S1;
    if (p *( mid - first) <= 100) // Too few points left to split
    {     for ( i = first; i < last; i ++)
            for ( j = i + 1; j < last; j ++)
                S1 . insert( line( X [ i ], Y [ i ], X [ j ], Y [ j ]));
    }
    else
    {     S1 = findlines( first , mid , p);
        set < line > S2 = findlines( mid , last , p);
        S1 . insert( S2 . begin (), S2 . end());
    }
    set < line >:: iterator it;
    for ( it = S1 . begin(); it != S1 . end(); it ++)
    {     a = it -> a;
       b = it ->b;
        c = it -> c;
        m = 0;
        for ( i = first; i < last; i ++)
            if ( a * X [ i ] + b * Y [ i ] == c)
                m ++;
        if ( 100 * m >= p *( last - first))
           S . insert( * it);
    }
    return S;
}

int main()
{     int n , p , i;
    scanf( "%d %d" , &n , &p);
    for ( i = 0; i < n; i ++)
        scanf( "%d %d" , & X [ i ], & Y [ i ]);
    printf( "%spossible \n " , n == 1 || ! findlines( 0 , n , p ). empty() ? "" : "im");
    return 0;
}

 

这篇关于随机算法 - HNU 13348 Finding Lines的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139561

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第