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;
}