牛客 Fruit Ninja 随机大法
链接:https://ac.nowcoder.com/acm/contest/163/A
来源:牛客网
题目描述
Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy,
splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.
Fruit Ninja is a very popular game on cell phones where people can enjoy cutting the fruit by touching the screen.
In this problem, the screen is rectangular, and all the fruits can be considered as a point. A touch is a straight line cutting
thought the whole screen, all the fruits in the line will be cut.
A touch is EXCELLENT if MN\frac{M}{N}NM ≥ x, (N is total number of fruits in the screen, M is the number of fruits that cut by the touch, x is a real number.)
Now you are given N fruits position in the screen, you want to know if exist a EXCELLENT touch.
输入描述:
The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
The first line of each case contains an integer N (1 ≤ N ≤ 104) and a real number x (0 < x < 1), as mentioned above.
The real number will have only 1 digit after the decimal point.
The next N lines, each lines contains two integers xi and yi (-109 ≤ xi,yi ≤ 109), denotes the coordinates of a fruit.
输出描述:
For each test case, output "Yes" if there are at least one EXCELLENT touch. Otherwise, output "No".
示例1
输入
复制
2
5 0.6
-1 -1
20 1
1 20
5 5
9 9
5 0.5
-1 -1
20 1
1 20
2 5
9 9
输出
复制
Yes
No
题意:是否存在直线上的点数 / n >= x
题解:随机500次,找出两个点,然后判断这条线上的点数。神奇不。因为如果某条直线上有很多点,那么随机到这条线的概率就会很大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
ll x[N], y[N];
int n;
double p;
int main() {int T;int l, r;int cnt;int flag;scanf("%d", &T);while(T--) {scanf("%d %lf", &n, &p);for(int i = 1; i <= n; i++) scanf("%lld %lld", &x[i], &y[i]);flag = 0;for(int i = 1; i <= 500; i++) {l = rand() % n + 1;r = rand() % n + 1;if(l == r) continue;cnt = 0;for(int j = 1; j <= n; j++) {if((x[j] - x[l]) * (y[r] - y[j]) == (x[r] - x[j]) * (y[j] - y[l])) cnt++;}if(1.0 * cnt / n >= p) {flag = 1;break;}}printf(flag ? "Yes\n" : "No\n");}return 0;
}
相关文章:

HDU - 6242 Geometry Problem 随机数
题目链接:https://vjudge.net/problem/HDU-6242 题意:n个点,找到一个圆,满足圆上点的数目大于等于⌈N / 2⌉ 题解:三个不在一条直线上的点确定一个圆,随机到圆上点的概率是1 / 2,那么三次就是…...

HDU - 6393 Traffic Network in Numazu 树上倍增求lca+dfs序+线段树
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid6393 题意:n个点n条边的图,求两点间的最小距离 题解:如果是一个树的话,那么我们就可以倍增dfs序,然后用线段树维护下就可以了这样是nlogn的复杂度&a…...

CodeForces - 1220D Alex and Julian 二分图性质
题目链接:https://vjudge.net/problem/CodeForces-1220D 题意:n个数,如果节点 i 和 j 满足 |i - j | 属于B,则i和j有一条边,问B集合最少删除多少边,使得得到的图是个二分图 题解:根据二分图的…...

CodeForces - 1220E Tourism 无向图缩点+树形dp
题目链接:https://vjudge.net/problem/CodeForces-1220E 题意:n个点m条边的无向连通图,起点s,每个点有权值,求遍历无向图得到的最大权值和。但是不能走回头路,即如果从U走到V那么下一步不可以从V走到U 题…...

HDU - 6156 Palindrome Function 数位dp
题目链接:https://vjudge.net/problem/HDU-6156 题意:区间[L, R]的数,写成k进制(l<k<r)后,如果是回文串,那么f(x,k)k,否则f(x,k)1,对f求和 题解:一看这种题就是数位dp,当时想…...

HDU - 6153 A Secret 扩展kmp
题目链接:https://vjudge.net/problem/HDU-6153 题意:对于s2的每一个后缀,假设长度为l,在s1出现的次数为k,求l*k的和 题解:我们把两个串都倒过来,变为s1,s2,那么问题就变为&#x…...

Gym - 100589A Queries on the Tree 树状数组+分块
题目链接:https://vjudge.net/problem/Gym-100589A 题意:n个点,根节点为1的树,两种操作,1 L y 与根节点距离为L的节点权值全部加上y,2 x x子树的权值总和 题解:对于更新操作,因为更…...

HDU-6731 Angle Beats 计算几何 直角三角形个数
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid6731 题意:n个点,m次查询,每次给你一个点,从n个点挑出两个能组成多少直角三角形 题解:假设询问的是点p,直角可能是p也可能是其他两点的某…...

HDU - 5927 Auxiliary Set dfs序+瞎搞
题目链接:https://vjudge.net/problem/HDU-5927 题意:给一棵树,然后每次询问时给出哪些点是不重要的点,让求这棵树上重要的点以及是两个不同的重要的点的lca一共有多少个 题解:我们只需要看给出的每一个不重要的点是不是重要的点就可以了&a…...

CodeForces - 689D Friends and Subsequences ST表+二分
题目链接:https://codeforces.com/problemset/problem/689/D 题意:有多少区间[l, r]满足,max(al..ar) min(bl..br) 题解:对于先固定l,那么对于max(a),是一个递增的序列,对于min(b)是一个递减…...

2017南宁 I. Rake It In dfs博弈
题目链接:https://nanti.jisuanke.com/t/A1538 题解:因为k只有3,所以最多取6次,每次有9种选取可能,所以直接dfs选取即可 #include <bits/stdc.h> using namespace std; typedef long long ll; int b[6][6]; in…...

CodeForces - 369E Valera and Queries 树状数组+离线+容斥思想
题目链接:https://vjudge.net/problem/CodeForces-369E 题意:n条线段,m次询问,给出cnt个点,问这些点在多少线段上 题解:如果每个点对于所在的线段上没有影响的话,那么我们就可以建立权值线段树…...

Gym - 101889I Imperial roads 树链剖分+最小生成树之必选一边
题目链接:https://vjudge.net/problem/Gym-101889I 题意:n个点,m条边,q次询问,每次必须选一边,求最小生成树的权值 题解:我们先跑一边最小生成树,然后按照最小边建树,必…...

CodeForces - 1228C Primes and Multiplication 数贡献
题目链接:https://vjudge.net/problem/CodeForces-1228C 题解:把x的每个质因子找出来,计算n!对每个因子的贡献 #include <bits/stdc.h> using namespace std; typedef long long ll; const ll mod 1e9 7; const int N …...

CodeForces - 1228D Complete Tripartite 图上的哈希
题目链接:https://vjudge.net/problem/CodeForces-1228D 题解:我们把每个点哈希,这样就能计算出和每个点连接的其他点的总哈希值,若只有三种哈希值的和,那么就是符合的,当然还有其他很多种做法。 #includ…...

2017 ICPC Asia Urumqi I. A Possible Tree 带权并查集
题目链接:https://nanti.jisuanke.com/t/40520 题解:因为他们都是联通的且只有唯一路径,所以不用管之前怎么连的,直接按照他给的查询,带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

HDU - 5923 Prediction 多个并查集
题目链接:https://vjudge.net/problem/HDU-5923 题解:因为n只有500个,所以我们可以每个点维护一个并查集,所以判断某些点的时候,这些并查集在合起来即可 #include <bits/stdc.h> using namespace std; const int N 510; struct edge…...

2018徐州 Gym - 102028J Carpets Removal 概率事件+二维差分
题目链接:https://vjudge.net/problem/Gym-102028J 题意:去掉两个矩形,让剩下的矩形覆盖的点最少 题解:使剩下的点少,那么我们就是去掉的两个矩形覆盖的尽可能多,也就是两个矩形各自占据的格子和只有两个…...
Gym - 102307J Jail Destruction 线段树
题目链接:https://vjudge.net/problem/Gym-102307J The semester has just begun at Universidad Nacional (UNAL). As usual, a group of vandals enjoys bringing chaos to all students and damaging the university facilities. Those guys have been planning…...

Gym - 101955L Machining Disc Rotors 计算几何 圆剩余部分直径
题目链接:https://vjudge.net/problem/Gym-101955L 题意:n个圆和 圆(0,0,R) 部分相交,求剩余圆的直径 题解:如果剩余部分存在直径的话,那就是2*R,这个怎么判断呢,对于每…...

Gym - 102307E Extreme Image 线段树 扫描线
题目链接:https://vjudge.net/problem/Gym-102307E 题意:平面上n个点,给定区域的w和d范围,求区域最大的点数 题解:其实和在平面上给定长和宽 是一样的道理,这个只需要对角度排序,然后对于每个…...

Gym - 102307C Common Subsequence dp
题目链接:https://vjudge.net/problem/Gym-102307C 题意:两个字符串的匹配长度能不能达到99%; 题解:因为n为1e5,所以不能直接dp[i][j]表示到(i,j)的最长匹配长度了,因为失配的最多1000,因此dp…...

18南京 Gym - 101981M Mediocre String Problem 扩展kmp+马拉车
题目链接:https://vjudge.net/problem/Gym-101981M 题意:求 s的一个子串后面加上t的前缀为回文串并且满足|s| > |t| 的个数 题解:因为牵扯到了前缀和子串的问题,大体就能想到要用到扩展kmp,我们把s倒置࿰…...

CodeForces - 374D Inna and Sequence 线段树
题目连接:https://vjudge.net/problem/CodeForces-374D 题意:n次操作,先给出m个数,原先有一个空序列,每次操作给出一个数,为1或0都放在后面,为-1时,删除m个位置的数 题解ÿ…...

ICPC Asia HongKong 2017
南京已成炮灰,徐州加油! A:java二分 import java.math.*; import java.util.*; public class Main {public static void main(String [] args){Scanner cinnew Scanner(System.in);int t,n;BigInteger z,zn,znjyn,ans,tans,x,XBigInteger.O…...

1225 D. Power Products 哈希
题目链接:http://codeforces.com/problemset/problem/1225/D 题意:有多少种组合方式,使得两个数相乘 能写成 x^k 的形式 题解:首先x^k,x的每个素因子的数目都是k的倍数,那么我们就对于每个数的素因子个数…...

1080 F. Katya and Segments Sets 主席树
题目链接:https://codeforces.com/contest/1080/problem/F 题意:有k个线段所属在n个集合中,每次询问a b x y,问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内 题解:按照每个线段的有区间排序,然…...

Kattis - largesttriangle Largest Triangle 平面最大三角形面积
题目链接:https://vjudge.net/problem/Kattis-largesttriangle 题意:任意三点的最大三角形面积 题解:首先想到最大的面积应该出现在凸包上,然后就是枚举任意两点,能想到第三点是满足线性的,所以第三点线性…...

数据挖掘-k平均算法
/* 题目内容:实现k平均算法的代码,并且通过样例 代码: */ #include <bits/stdc.h> using namespace std; #define eps 1e-8 #define INF 0x3f3f3f3f const int N 1e6 10; int n, k; pair<double, double> a[N], b[N]; vector&l…...

初识matlab
简单的数学运算: 极限运算: limit(f,x,x0): 计算x→x0时函数f的极限。 举例: syms x y1(1x2*sin(x))^(2/x); y2((1x)^0.5-2)/(x^2-2*x-3); y3x^2*sin(1/x)/sqrt(2*x^2-1); f1limit(y1,0) f2limit(y2,3) f3limit(y3,inf…...

MATLAB学习知识整理 从入门到放弃
简介: Matlab: 美国MathWorks公司出品的商业数学软件。是一种高级技术计算语言和交互式环境。 主要用于: 算法开发 数据可视化 数据分析 数值计算 一、初识matlab 二、matlab数组运算与…...

matlab数组运算与数组化编程
matlab中的运算和操作主要是以数组为对象的, 数组又包括:数值数组、字符数组、元胞数组等。 一、数值数组的建立: 1. 直接输入法: 逗号:用来分开数组中的行元素。(可用空格代替) 分号&#…...

matlab程序设计
一、自定义函数 格式:函数句柄 (自变量列表)函数表达式 例1 定义函数,并计算f(x)在点x-2,1,2.5,3,5.2的值。 f(x)x.^23*x5 x[-2,1,2.5,3,5.2] y1f(x) 二、 m-文件函数(子程序) 格式:function [y1,y2]ff(x1,x…...

matlab数值计算
第一节 多项式运算 一、多项式的表示、求值、求根 1. 表示: matlab中把多项式表达成一个行向量,该向量中的元素是按多项式降幂排列的。 p[2,3,-1,4,5]表示多项式: 显示多项式的数学形式: p1poly2str(p,x) 如&…...

matlab图形功能
//...

python实现键盘输入多个值
Python 2里面读取输入的函数是raw_input(), Python 3的是input(),读入一个值后回车读取输入就退出了,想要一次读取多个输入,可以像下面这样: a, b raw_input().split()1 2a Out[224]: 1b Out[225]: 2 上面保存的是字…...

VS2019在win10下配置boost库
第一步:官网下下载:https://www.boost.org/users/history/version_1_73_0.html win10选择boost_1_73_0.zip 第二步:解压 第三步:编译 打开VS命令行 选择 已压缩好的boost_1_73_0文件夹 运行 bootstrap.bat 成功之后运行 刚…...

pthread_cond_wait()
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); 该函数第一个参数为条件变量指针,第二个为互斥量指针。该函数调用前,需本线程加锁互斥量,加锁状态的时间内函数完成线程加入等待队列操作 ,线程进入等待前…...

pthread多线程学习
基于pthread学习 多线程编程...
线程私有数据
线程私有数据实现的主要思想是:在分配线程私有数据之前,创建与该数据相关联的健,这个键可以被进程中的所有线程使用,但每个线程把这个键与不同的线程私有数据地址进行关联,需要说明的是每个系统支持有限数量的线程特定…...

创建线程的几种方式
class A {int x; public:void f(int x, char c) { };int operator()(int N) { return 0; } }; void foo(int x){} int main() {A a;thread t1(a, 6); // 传递a的拷贝给子线程thread t2(ref(a), 6); //传递a的引用给子线程thread t3(move(a), 6); //a在主线程中将不再有效threa…...

c++11多线程学习
一.join和detach C中的thread对象通常来说表达了执行的线程(thread of execution),这是一个操作系统或者平台的概念。 当thread::join()函数被调用后,调用它的线程会被block,直到线程的执行被完成。基本上࿰…...

Socket编程
C Socket 编程:https://blog.csdn.net/sinat_35866463/article/details/81019778 windows环境下用c实现socket编程:https://blog.csdn.net/xiaoquantouer/article/details/58001960 win7系统两台电脑之间利用Socket实现文件传输---C实现:ht…...

inet_pton()和inet_ntop()函数
https://blog.csdn.net/zyy617532750/article/details/58595700 1.把ip地址转化为用于网络传输的二进制数值 int inet_aton(const char *cp, struct in_addr *inp); inet_aton() 转换网络主机地址ip(如192.168.1.10)为二进制数值,并存储在struct in_addr结构中&a…...
C/C++内存泄漏及检测
“该死系统存在内存泄漏问题”,项目中由于各方面因素,总是有人抱怨存在内存泄漏,系统长时间运行之后,可用内存越来越少,甚至导致了某些服务失败。内存泄漏是最难发现的常见错误之一,因为除非用完内存或调用…...

八大设计模式原则
1.依赖倒置原则 高层模块不依赖底层模块,二者都应该依赖抽象 抽象不依赖实现细节,实现细节应该依赖于抽象 这一原则与下面的针对接口编程而不是针对实现编程是一个道理,我们设计一个程序,我们应该先想好我们想要抽象什么&#x…...

C++设计模式
管理变化, 提高复用 两种手段:分解 抽象 八大原则:https://blog.csdn.net/mmk27_word/article/details/108521903 重构技法: 静态 -> 动态 早绑定 -> 晚绑定 继承 -> 组合 编译时依赖 -> 运行时依赖 紧耦合 ->…...

LRU算法
#include <iostream> #include <list> #include <map> using namespace std; class LRU {struct node {int key, val;node(int k_ 0, int v_ 0) {key k_;val v_;}};public:int cap; // 大小map<int, list<node>::iterator> mp;list<node&…...
数据库事务四个特性
ACID特性 数据库管理系统中事务(transaction)的四个特性(分析时根据首字母缩写依次解释):原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性…...
Git入门简介
本文简单介绍一下Git的使用,主要内容有下: Git基本介绍Git相较于SVN的优势Git使用流程及常用命令 Git基本介绍 Git是一款免费、开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目 —— [ 百度百科 ] GitHub:https…...