本文主要是介绍UVA 11186 - Circum Triangle（圆上三角形求法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题 感觉数据是500 就直接三层循环上去了。 。但是超时了。 我用了最简单的方法 可能是运算量略大的原因吧。（好吧。 在自己稍微优化之后A了。 跑了2.059秒，代码在最后面）
在不会优化的情况下。 去网上搜了题解。
第一份代码。 在我看明白之后 不得不佩服 原作者的聪明机智。 也算是 学到了。
先上代码后讲解。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 1001
#define INF 1<<30
double p = acos(-1);
struct po{double x,y;
} s[maxn];
int main (){int n;double r;while(scanf("%d%lf",&n,&r) != EOF && n && r) {double f[maxn];for(int i = 0; i < n; i++){scanf("%lf",&f[i]);f[i] = f[i]/180.0*p;}sort(f,f+n);double sum = 0;for(int i = 0; i < n-1; i++){for(int j = i+1; j < n; j++){sum += (n + 2*i - 2*j)*sin(f[j] - f[i]);}}sum = sum * r * r / 2;sum = floor(sum+0.5);printf("%lld\n",(ll)sum);}return 0;
}
在这个代码中。 大体思路是很清晰的。 就是找出 每个点 所与x正半轴的夹角。 然后 在sum中 sin（f【j】 - f【i】） 与后面 sum * r*r /2
便可以知道 用的是 a*b*sin（c）/ 2 这个公式。 但是前面 的 （n+2*i- 2*j） 似乎很难理解。
自己没有看出来。 找了川神 他看了一会给我讲解的。
在上图中。 我们假定要求 S（i，j，k） 如果k在 j的左侧 那么 S（i,j,k） = S(i,k,o)+s(i,j,o) - s(k,i,o); 显然 只要k在j的左侧 s（i，j，0） 在用来求 做和用的。
如果k在 j的右侧 那么 S（i,j,k） = S(i,k,o)+s(i,j,o) - s(k,j,o); 显然 只要k在j的右侧 s（i，j，0） 在用来求 做和用的。
如果k在 i，j的中间 那么 S（i,j,k） = S(j,k,o)+s(i,k,o) - s(i,j,o); 显然 只要k在i，j的中间 s（i，j，0） 在用来求 做差用的。
那么 我们就可以对于 线段 i，j 对于后面 或者前面的点来说 都需要加上oji 这一块面积 而对于 ij 中间的 点来说 都需要 减去这一块。
那么对于这一块面积。 总共的 需求为 当k在左侧的时候 ： n - j - 1 k在右侧是时候 为 i 加起来为 n - j + i - 1；
对于k位于中间来说。 总共需要减去 个数为 j - i - 1个。
那么 总共就是 n + 2i - 2j 个。 乘上 这一块的面积 sin（c） 就OK了
上面的公式也就推出来了。
下面是自己写的那个代码。。 最简单了。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 1001
#define INF 1<<30
double p = acos(-1);
struct po{double x,y;
};
po s[maxn];
double l[maxn][maxn];
double ss;
double line(int i,int j){return sqrt((s[i].x - s[j].x) * (s[i].x - s[j].x) + (s[i].y - s[j].y) * (s[i].y - s[j].y));
}
int main (){int n;double r;double jiao;while(scanf("%d%lf",&n,&r) != EOF && n && r){for(int i = 0; i < n; i++){scanf("%lf",&jiao);jiao = jiao/180*p;s[i].x = r * cos(jiao);s[i].y = r * sin(jiao);}for(int i = 0; i < n-1; i++){for(int j = 0; j < n; j++){l[i][j] = line(i,j);l[j][i] = l[i][j];}}double sum = 0;for(int i = 0; i < n-2; i++){for(int j = i+1; j < n-1; j++){for(int k = j+1; k < n; k++){ss = (l[i][j]+l[i][k]+l[j][k])/2.0;sum += sqrt(ss*(ss-l[i][j])*(ss-l[i][k])*(ss-l[j][k]));}}}printf("%.0lf\n",sum);}return 0;
}
这篇关于UVA 11186 - Circum Triangle（圆上三角形求法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
