Fruit Ninja

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 ≤ 10⁴) 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 x_i and y_i (-10⁹ ≤ x_i,y_i ≤ 10⁹), denotes the coordinates of a fruit.

C++11(clang++ 3.9) 解法, 执行用时: 598ms, 内存消耗: 604K, 提交时间: 2018-08-08 19:05:25

#include<iostream>
using namespace std;
double x[10010],y[10010];
int n;
double k;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lf",&n,&k);
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf",&x[i],&y[i]);
		}
		int flag=0;
		for(int i=0;i<1000;i++)
		{
			int a=rand()%n;
			int b=rand()%n;
			if(a==b)
				continue;
			int cnt=0;
			for(int j=0;j<n;j++)
			{
				if((y[j]-y[a])*(x[a]-x[b])==(x[j]-x[a])*(y[a]-y[b]))		
					cnt++;	
			}
			if(10*cnt>=10*n*k)
			{
				flag=1;
				break;
			}
		}
		if(flag)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 897ms, 内存消耗: 604K, 提交时间: 2018-08-08 16:30:36

#include <bits/stdc++.h>
using namespace std;
struct Point{
	long long x,y;
}a[10005];
int main()
{
	srand(time(NULL));
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		double x;
		cin >> n >> x;
		for(int i=0;i<n;i++)
			cin >> a[i].x >> a[i].y ;
		int i;
		for(i=0;i<100;i++)
		{
			int M = 0;
			int q = rand()%n;
			int w = rand()%n;
			if(q==w)continue;
			for(int j=0;j<n;j++)
			{
				if((a[j].y-a[q].y)*(a[w].x - a[q].x) == (a[j].x - a[q].x)*(a[w].y-a[q].y))
					M++;
			}
			if(1.*M/n >= x) 
			{	
				cout <<"Yes"<<endl;
				break;
			}
		}
		if(i==100)cout << "No" << endl;
	}
	return 0;
}

详情