题解 - Vijos

2

doc LV 10 MOD @ 8 年前

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

因为是直角三角形，答案应该恰好就是 $13*84/2=546$ 。

1

hzk123 LV 9 @ 7 年前

#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

hyl LV 10 @ 12 年前

good

0

voyagec2 LV 10 @ 15 年前

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

二分半径

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

0

curimit LV 10 @ 15 年前

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

0

fengyi LV 9 @ 16 年前

精度很恶心

我做特殊处理才过的

0

BB牛 LV 8 @ 16 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

sunheming @ 4 年前

nhml
sunheming @ 4 年前

sqlm

0

NarcissuRD LV 3 @ 16 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

数学题+二分

0

Iek.Chan LV 4 @ 16 年前

URAL p_1159

0

pzy3303 LV 10 @ 16 年前

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

0

skyinde2 LV 4 @ 16 年前

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

样例是不是有问题.

0

jimistdponde LV 8 @ 16 年前

我也想出题

可是vijos 上面不能交compare

。。。。。

0

frostmourn LV 4 @ 16 年前

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

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

不过姑且没想法....

0

188513911 LV 9 @ 16 年前

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

诡异！

0

bochuan007 LV 3 @ 16 年前

超时。。。

0

cgy4ever LV 10 @ 16 年前

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

1159 C++ Accepted

0.015 249 KB

//

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

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

然后二分求半径

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

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

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

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

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

0

FDhyc LV 10 @ 16 年前

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

0

orz教主_tangky LV 7 @ 16 年前

ACM ICPC 2001. Northeastern European Region, Northern Subregion

0

T.-T LV 3 @ 16 年前

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

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

0

linshutan LV 3 @ 16 年前

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)

题解

29 条题解

栅栏

信息

状态

开发

支持

题解

29 条题解

栅栏

信息

状态

开发

支持

还没有账户？

登录