I、Expected Size of Random Convex Hull

NC17248. I、Expected Size of Random Convex Hull

描述

Currently, Eddy is reading this paper "On the Expected Complexity of Random Convex Hulls"(1997). It states that the expected number of vertices of the convex hull of N points, chosen uniformly and independently from a disk is $O(N^{\frac{1}{3}})$ , and $O(K \log N)$ for the case a convex polygon with K sides, and so on. Eddy thinks it's very interesting and now wants to research something about it. But, it seems too hard to start with something like disk or polygon.

Thus, as his first step in the research, Eddy first chooses a triangle. Now, Eddy wants to find out the expected number of points on the convex hull when uniformly randomly picking N points within the triangle. However, Eddy can't find any way to solve this problem. As his best friend, you come to help Eddy finish his research debut.

输入描述

For first three lines, each contains two space-separated integer x_i, y_i indicating the points(x_i, y_i) of the triangle Eddy chooses.
Forth line contains one integer N indicating that N points will be randomly uniformly chosen within the given triangle.

-10⁹ ≤ x_i, y_i ≤ 10⁹
3 ≤ N ≤ 10
It's guaranteed that given input forms a non-degenerate triangle

输出描述

Output a floating number indicating the expected number of points on the convex hull.

Absolutely or relatively error within 10^-4 will be considered correct.

示例1

输入:

输出:

3.000000000000

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2018-07-26 16:24:14

#include<cstdio>
using namespace std;
int main()
{
	int a;
	for(int i=1;i<=6;i++)scanf("%d",&a);
	int n;
	scanf("%d",&n);
	double ans=3;
	for(int i=3;i<n;i++)ans+=2.0/i;
	printf("%.5f\n",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2018-07-26 16:41:14

#include<stdio.h>
int t=7,n;float s;int main(){while(t--)scanf("%d",&n);while(n-->1){s+=2.0/n;}printf("%.4f\n",s);}

Python3(3.5.2) 解法, 执行用时: 35ms, 内存消耗: 3432K, 提交时间: 2018-07-26 21:03:34

for i in 'iiii':
    n = input()
print(sum(2 / i for i in range(1, int(n))))

上一题

下一题

详情