HDU 4978 计算凸包

有以无限间隔$D$的水平线分割的平面，在上面随机投下一个圆，圆中有一些点，点之间两两成一条线段，问随机投下至少有一条线段于平行线相交的概率。

以下是不严(luan)谨(lai)的思路。

首先都知道对于任意长度$L$的线段随机投放在无数间隔为$D$的平面，其有相交情况的概率为$\frac{2L}{D\pi}$（浦丰投针）
首先考虑线段是垂直平行线的不会发生旋转（固定角度）其随机投放在平面上有交点的概率为$\frac{L}{D}$，
但是实际情况是线段会旋转,其对应在垂直平行线上的投影长度的期望为$\frac{2L}{\pi}$,重新代入到$L$就是上面那个概率公式，
现在由于圆内点两两间都有线段，要考虑圆内为一个整体，不妨直接拿多边形的边（因为其他线段的投影都在其投影内）来计算它们的投影长度的期望，得到的结果其实也就是点集凸包的周长除以$\pi$
然后代入:$\frac{c}{D\pi}$ ，会发现是个水题

/** @Date    : 2017-09-24 22:35:19

  * @FileName: HDU 4978 凸包 计算.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

const double Pi = acos(-1.0);

struct point

{

	double x, y;

	point(){}

	point(double _x, double _y){x = _x, y = _y;}

	point operator -(const point &b) const

	{

		return point(x - b.x, y - b.y);

	}

	double operator *(const point &b) const

	{

		return x * b.x + y * b.y;

	}

	double operator ^(const point &b) const

	{

		return x * b.y - y * b.x;

	}

};

double xmult(point p1, point p2, point p0)

{

    return (p1 - p0) ^ (p2 - p0);

}  

double distc(point a, point b)

{

	return sqrt((double)((b - a) * (b - a)));

}

int sign(double x)

{

	if(fabs(x) < eps)

		return 0;

	if(x < 0)

		return -1;

	else

		return 1;

}

////////

int n;

point stk[N];

point p[N];

int cmpC(point a, point b)//水平序排序

{

	return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);

}

int Graham(point *p, int n)//水平序

{

	sort(p, p + n, cmpC);

	int top = 0;

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

	{

		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0)

			top--;

		stk[top++] = p[i];

	}

	int tmp = top;

	for(int i = n - 2; i >= 0; i--)

	{

		while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,p[i] )) < 0)

			top--;

		stk[top++] = p[i];

	}

	if(n > 1)

		top--;

	return top;

}

int main()

{

	int T;

	cin >> T;

	int c = 0;

	while(T--)

	{

		int n;

		double d;

		cin >> n >> d;

		double x, y;

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

		{

			scanf("%lf%lf", &x, &y);

			p[i] = point(x, y);

		}

		int m = Graham(p, n);

		double ans = 0.0;

		stk[m++] = stk[0];//注意只有直线的情况

		for(int i = 0; i < m - 1; i++)

			ans += distc(stk[i], stk[i + 1]);

		printf("Case #%d: %.4lf\n", ++c, ans / d / Pi);

	}

    return 0;

}

巴特西

HDU 4978 计算凸包

最新文章

热门文章

巴特西

HDU 4978 计算 凸包

最新文章

热门文章

HDU 4978 计算凸包