当前位置: 代码迷 >> 综合 >> Circum Triangle(圆上三角形)
  详细解决方案

Circum Triangle(圆上三角形)

热度:29   发布时间:2023-11-24 03:58:15.0

UVA 11186

题目大意:给出一个圆,在圆上有n个点,给出每个点的角度(相当于坐标)
求出每三个点围成的面积之和!

分析
给出点的数量是500,最简单的思路就是三层for循环直接枚举三个点然后求和
但是这样会超时,所以必须要想办法优化!

我们就要利用 所有的点,都在圆上这一信息!

图解
如果现在拿出三个点 i ,j ,k 组成一个三角形
那么 Sijk 有如下关系

请添加图片描述
那么就说明不管 k是在左边还是右边,都需要 减去Sijo
当k在中间时,则需要 加上 Sijo

所以我们可以对 所有的点 按照 弧度大小 排序

每次只枚举两个点 分别是 i,j ( j的弧度大,i的弧度小)

那么 就会有 n-j 个点 在j的左侧
然后有 i-1个点在右侧

所以总共有 n-j+i-1 需要减去 Sijo

并且有 j-i-1 个点在中间
那么就有 j-i-1 个 需要加上 Sijo

所以 总共需要 n-2 * j-2 * j 个 Sjio
那么根据三角形面积公式 S=1/2 * a * b * sinc

则有 0.5 * r * r * sin ( a[j]-a[i] )*(n- 2 * j * 2 * i )
即为 i,j贡献的所有面积值!

然后不断枚举然后累加
最后利用 floor(ans+0.5) 取最接近的整数即为答案!

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;double r;while(cin>>n>>r&&n&&r){double a[500];for(int i=0;i<n;i++){cin>>a[i];a[i]=a[i]/180*acos(-1);  //转换成弧度制!,转换成弧度制之后才能用三角函数! }sort(a,a+n);double num=0;for(int i=0;i<n-1;i++)//本题核心内容! for(int j=i+1;j<n;j++)num+=(n+2*i-2*j)*sin(a[j]-a[i]);//这里用了一个非常巧妙的数学推理!!! num=0.5*r*r*num;// 1/2*r*r*num;   //利用了一个公式! 1/2 *a*b*sinc//二分之一*a*b*sinc! num=floor(num+0.5);//这样就可以取最接近的整数了!,就不用写那么麻烦了!!//num=floor(num+0.5) 即为取最接近的整数!!! printf("%lld\n",(long long)num);}return 0;
}