/ Vijos / 题库 / 栅栏 /

题解

29 条题解

  • 1
    @ 2017-03-03 01:18:49

    因为精度问题,在最后计算面积的时候,要谨慎使用sin, cos等函数,甚至sqrt也不例外。
    我手动写了二分到\(\epsilon = 10^{-8}\)的开根号。可以尝试考虑下面的数据。

    3
    13
    84
    85
    

    因为是直角三角形,答案应该恰好就是\(13*84/2=546\)。

  • 0
    @ 2017-10-04 16:41:28
    #include <bits/stdc++.h>
    #define  eps 1e-10
    using namespace std;
    const long double pi=acos(-1);
    long double l[222];
    int n;
    int dcmp(long double x)
    {
       if (fabs(x)  < eps ) return 0;
       else return x>0 ? 1 : -1;
    }
    long double calc(long double r)
    {
       long double angle=0;
       for (int i=1;i<=n;i++)
          angle += acos( 1 - 0.5 * l[i] * l[i] / (r * r));
       return angle;
    }
    
    long double calc2(long double r)
    {
       long double angle=0;
       for (int i=1;i<=n-1;i++)
          angle += acos( 1 - 0.5 * l[i] * l[i] / (r * r));
       angle = acos( 1 - 0.5 * l[n] * l[n] / (r * r)) - angle;
       return angle;
    }
    int main()
    {
    
       scanf("%d",&n);
       for (int i=1;i<=n;i++)
          cin>>l[i];
    
       sort(l+1,l+1+n);
       long double tot=0;
       for (int i=1;i<n;i++)
          tot += l[i];
       if (tot <= l[n])
       {
          printf("0.00\n");
          return 0;
       }
       long double L=l[n]/2,R=2000;
       long double area=0;
        if (calc(L)/2 > pi)
       for (int _=0;_<66;_++)
       {
             long double  mid=(L+R)/2;
             if  ( calc(mid) < 2 * pi )  R = mid;
             else L = mid;
           area=0;
          for(int i=1;i<=n;i++)
             area +=  sqrt( R * R  - l[i] * l[i] / 4) * l[i] / 2;
       }
       else
        {
           for (int _=0;_<66;_++)
           {
              long double mid=(L+R)/2;
              if ( calc2(mid) > 0 )  L = mid;
              else R=mid;
           }
           area=0;
           for(int i=1;i<n;i++)
              area +=  sqrt( R * R  - l[i] * l[i] / 4) * l[i] / 2;
           area -= sqrt(R * R - l[n]*l[n]/4) * l[n] /2;
        }
       cout.setf(ios::fixed);
       cout.precision(2);
    
    
    
       cout<<area<<endl;
    }
    
  • 0
    @ 2013-03-19 21:25:20

    good

  • 0
    @ 2010-03-11 18:57:24

    以最大边为直径,计算出其他所有边的圆心角,若小于180,则圆心在图形外

    二分半径

    PASCAL用ARCTAN,用底*高,别用海伦公式算面积,精度限定在1E-6以内就行了

  • 0
    @ 2009-04-15 15:54:30

    还要分圆心在内和圆心在外两种情况讨论呢。。。。。

  • 0
    @ 2008-11-10 20:33:52

    精度很恶心

    我做特殊处理才过的

  • 0
    @ 2008-11-07 10:12:19

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:运行超时...

    ├ 测试数据 04:运行超时...

    ├ 测试数据 05:运行超时...

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:20 有效耗时:0ms

  • 0
    @ 2008-10-23 21:20:03

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    数学题+二分

  • 0
    @ 2008-10-14 11:30:43

    URAL p_1159

  • 0
    @ 2008-10-13 17:32:08

    做了这题,你就知道这道题的精度有多恶心了

  • 0
    @ 2008-10-10 20:37:57

    连样例都没过的程序交上去一遍AC,汗一个...

    样例是不是有问题.

  • 0
    @ 2008-10-08 12:56:23

    我也想出题

    可是vijos 上面不能交compare

    。。。。。

  • 0
    @ 2008-10-07 22:18:00

    我看到了猥琐的琛哥很嚣张的说是水题,

    小junjie又说难度不止为1,看来这个题是潜力题..

    不过姑且没想法....

  • 0
    @ 2008-10-07 20:38:48

    我去掉计算圆心在图形外的程序段就AC,加上就只有40

    诡异!

  • 0
    @ 2008-10-06 21:51:21

    超时。。。

  • 0
    @ 2008-10-07 18:38:20

    ural1159过了,下面那个bt数据得了个超大的数,估计哪出问题了...

    1159 C++ Accepted

    0.015 249 KB

    //

    这道题挺有意思的,还没有做的朋友不要看题解自己先想想吧.

    我是用物理模型得到的,它应该是圆内接图形

    然后二分求半径

    注意圆心在图形内和图形外的两种情况

    还有,二分的范围要比较大,开始是[ max(xi)/2 , 1000] 结果错了

    后来才知道,这个半径可以比较大的

    还有,判断能否构成多边形,如果不能,要输出字符串"0.00"

    我之前输出 0.00 结果挂了.或者把设置精度写在这之前也没问题了.

  • 0
    @ 2008-10-06 16:29:11

    本题的AC率是我刷下来的!Oh yeah!

  • 0
    @ 2008-10-06 15:18:33

    ACM ICPC 2001. Northeastern European Region, Northern Subregion

  • 0
    @ 2008-10-06 14:23:00

    莫涛哪儿弄来的题,我搜了半天就只在csdn里找到一~

    那里有人回的,题解就是楼下的,只是那人是用C++实现的~

  • 0
    @ 2008-10-06 13:03:17

    program p1463;

    var l:array[0..300]of real;

    sum,n,i,j,k,max1:integer;

    s:real;

    function max(a,b:real):real;

    begin

    if a>b then max:=a else max:=b;

    end;

    function hairun(a,b,c:real):real;

    var p:real;

    begin

    if (a+b+c)

信息

ID
1463
难度
7
分类
计算几何 | 几何知识 点击显示
标签
(无)
递交数
113
已通过
25
通过率
22%
上传者