首页 > ACM题库 > HDU-杭电 > HDU 4682-The Happy Triangles-计算几何-[解题报告]HOJ
2015
09-17

HDU 4682-The Happy Triangles-计算几何-[解题报告]HOJ

The Happy Triangles

问题描述 :

Alice has a toy, which was made up by two parts. The first part is a frame consisting of one horizontal stick and two vertical sticks. The distance between the two vertical sticks is R. And the horizontal stick is long enough. The second part of her toy is N triangles. These triangles can be fastened on the frame with one of their edges on the horizontal stick. Once they are fastened, they can slide along the horizontal stick. And magically, they can overlap each other. (See pic 1)
Now, Alice wants to maximize the total area covered by these triangles between the two vertical sticks.
Note :
1. The triangles DON’t have to be totally between the two vertical sticks. But the area out of the two sticks should not be taken into consideration.
2. These triangles are either acute triangle or right triangle.
String

输入:

There are several cases. The first line of the input is a single integer T. (T<=100)
For each case, the first line contains two integers N ,R. (N<=1000,R<=100000)
The next N lines, each line contains three integer a,b,c , which stand for the lengths of three edges of the i-th triangle.
(0<a<=b<=c<100000,a2+b2>=c2).

输出:

There are several cases. The first line of the input is a single integer T. (T<=100)
For each case, the first line contains two integers N ,R. (N<=1000,R<=100000)
The next N lines, each line contains three integer a,b,c , which stand for the lengths of three edges of the i-th triangle.
(0<a<=b<=c<100000,a2+b2>=c2).

样例输入:

2 
1 5
3 4 5
2 4
3 4 5
3 4 5

样例输出:

Case #1: 6.000
Case #2: 10.667

二分法的好题,推荐!

题目见http://acm.hdu.edu.cn/showproblem.php?pid=4682

解法需要先证明两个结论,这两个结论都是基于最优策略的,可以证明若不满足这两个条件中的任一个都可以通过调整使其变得更优。

1. 每个三角形都应该把最短边与底线重合。

2. 存在重叠时,所有三角形之间的交点以及三角形与左右两条竖线的交点应该在同一水平线上。

(证明的话,我就不赘述了,详见解题报告。其实很简单,自己YY下也可以证明的。)

知道这两点,然后只需要二分交点的高度就可以了。

PS:这题的精度要求虽然只有小数点后3位,但是由于大量的计算,实际对精度的要求很高,因此对采用的算法也有一点要求。

#include <cstdio>
#include <cmath>
const int maxn = 1010;
const double PI = acos(-1.0);
const double eps = 1e-9;

int T, cas = 1, n;
double r, a[maxn], b[maxn], c[maxn];
double area[maxn], height[maxn];

double f(double h)
{
    double ret = 0;
    for (int i=1;i<=n;i++)
        if (h < height[i]) ret += a[i] * (1.0 - h / height[i]);
    return ret;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%lf", &n, &r);
        for (int i=1;i<=n;i++) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
        for (int i=1;i<=n;i++)
        {
            double p = (a[i] + b[i] + c[i]) / 2;
            area[i] = sqrt(p * (p-a[i]) * (p-b[i]) * (p-c[i]));
            height[i] = area[i] * 2 / a[i];
        }
        double low = 0, high = 100000, mid;
        int tt = 60;
        while (tt--)
        {
            mid = (low + high) / 2;
            if (f(mid) <= r) high = mid;
            else low = mid;
        }
        double ans = 0, h = mid;
        for (int i=1;i<=n;i++)
            if (h < height[i]) ans += area[i] - h*a[i]*(h/height[i])/2;
        printf("Case #%d: %.3lf\n", cas++, ans);
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/huangshenno1/article/details/10034879