首页 > ACM题库 > HDU-杭电 > HDU 3558-Easy Geometry[解题报告]HOJ
2014
11-05

HDU 3558-Easy Geometry[解题报告]HOJ

Easy Geometry

问题描述 :

There are a set of points in the plane. Dumbear will choose some of them and find the convex hull of the chosen points. For each point, we know that probability that Dumbear will choose it. We want to know the expected number of vertexes the convex hull had.
You can assume that any three points are not in the same line. If the number of the chosen points is smaller than three, we think all the chosen points are vertexes of the convex hull.

输入:

There are several test cases in the input.
The first line of each test case contains an integer n (1<=n<=1000). n lines follow, each line contains three integers x, y and p (1<=x, y<= 100000, 0 <= p < 100) indicating a point at (x, y) and Dumbear will choose it with probability p%.
The input terminates by end of file marker.

输出:

There are several test cases in the input.
The first line of each test case contains an integer n (1<=n<=1000). n lines follow, each line contains three integers x, y and p (1<=x, y<= 100000, 0 <= p < 100) indicating a point at (x, y) and Dumbear will choose it with probability p%.
The input terminates by end of file marker.

样例输入:

1
1 1 50
3
1 1 99
1 2 99
2 3 0
4
1 1 50
5 1 50
1 5 50
2 2 50

样例输出:

0.50
1.98
1.94

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define eps 1e-8
#define PI 3.14159265358979323846
using namespace std;

//����
struct pt
{
	double x, y;
	double ang;
	double p;
};

//////////////////////////////////////////////////////

int n;
int idx[1010];
pt p[1010];

inline double toAng(double a, double b)
{
	double ret = b - a;
	if (ret > 2*PI - eps)
		ret -= 2*PI;
	return ret < -eps ? (ret + 2*PI) : ret;
}

bool cmp(int a, int b)
{
	return p[a].ang < p[b].ang;
}

double calc(int a)
{
	if (p[a].p < eps)
		return 0.0;
	double tp = 0.0;	
	int m = n - 1;
	for (int i = 0; i < n; i++)
	{
		if (i != a)tp += log(1.0 - p[i].p);
		p[i].ang = (i == a) ? 10.0 : atan2(p[i].y - p[a].y, p[i].x - p[a].x);
	}
	sort(idx, idx + n, cmp);
	double noP = 0.0, ret = 0.0;
	int r = 0;
	for (int i = 0; i < n - 1; i++)
	{
		while (r - i < m && toAng(p[idx[i]].ang, p[idx[r%m]].ang) < PI)
		{
//			printf("%d : %d\n", i, r);
			noP += log(1.0 - p[idx[r%m]].p);
			r++;
		}
		noP -= log(1.0 - p[idx[i]].p);
		ret += p[idx[i]].p * exp(noP);
	}
//	printf("%d -- %lf %lf %lf\n", a, p[a].p, ret, tp);
	return p[a].p * (ret + exp(tp));
}

double solve()
{
	if (n == 1)
		return p[0].p;
	double ans = 0.0;
	for (int i = 0; i < n; i++)
	{
		ans += calc(i);
//		printf("-- %lf\n", ans);
	}
	return ans;
}

int main()
{
	while (~scanf("%d", &n))
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].p);
			p[i].p /= 100.0;
			idx[i] = i;
		}
		printf("%.2lf\n", solve());
	}
	return 0;
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。