首页 > ACM题库 > HDU-杭电 > HDU 3201-Build a Fence-计算几何-[解题报告]HOJ
2014
03-06

HDU 3201-Build a Fence-计算几何-[解题报告]HOJ

Build a Fence

问题描述 :

Arborescence Counting

There is a wall in your backyard. It is so long that you can’t see its endpoints. You want to build a fence of length L such that the area enclosed between the wall and the fence is maximized. The fence can be of arbitrary shape, but only its two endpoints may touch the wall.

输入:

The input consists of several test cases.
For every test case, there is only one integer L (1<=L<=100), indicating the length of the fence.
The input ends with L=0.

输出:

The input consists of several test cases.
For every test case, there is only one integer L (1<=L<=100), indicating the length of the fence.
The input ends with L=0.

样例输入:

1
100
0

样例输出:

0.16
1591.55

题目大意:

长度为L的不封闭的曲线, 开口用线段连接, 求其最大面积.

 

简要分析:

小学数学有这么个结论吧: 封闭曲线周长相等时, 圆的面积最大. 于是我们猜想, 不封闭的曲线, 最优是不是半圆, 然后样例似乎就是这样的. 这个算法的严谨证明还没想到.

 

代码实现:

#include <cmath>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const double PI = acos(-1.0);
 int n;
 
 int main() {
     while (scanf("%d", &n) != EOF) {
         if (n == 0) break;
         printf("%.2lf\n", (n / PI) * (n / PI) * PI * 0.5);
     }
     return 0;
 }


参考:http://www.cnblogs.com/zcwwzdjn/archive/2012/02/25/2367354.html


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮