题目大意:给出若干个点,保证任意三点不共线,任意选三个点作为三角行,其他点若又在该三角形内,则算是该三角形内部的点,问所有情况的三角形平均每个三角形有多少个内部点。
解题思路:三角形的总数很容易求C(3n),现在就是要求各个三角形内部点的总数,同样我们可以反过来,求每个点在多少个三角形的内部。
然后我们确定一个点,求该点在多少个三角的内部,剩余n-1个点,可以组成C(3n−1])个三角形,所以只要求出该点在哪些三角形的外部即可。
红色点为选中的点,将周围点按照与选中点的极角进行排序,每次枚举一点,它的极角为a,所有极角小于a+pi的点,这些点组成的三角形,选中点一定在外部。处理一周的方式是将点的数组扩大两倍,将所有点的极角加上pi有保留在延长的数组中。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1205;
const double pi = 4 * atan(1.0);
const double eps = 1e-9;
int n;
double s, r[2*N];
struct point {
double x, y;
}p[N];
double Count (int d) {
int c = 0, mv = 0;
for (int i = 0; i < n; i++) {
if (i == d)
continue;
double a = atan2(p[i].y-p[d].y, p[i].x-p[d].x);
r[c] = a;
r[c+n-1] = a + 2*pi;
c++;
}
c = 2 * n - 2;
sort(r, r + c);
double ans = 0;
for (int i = 0; i < n-1; i++) {
double tmp = r[i] + pi;
while (tmp > r[mv])
mv++;
double cnt = mv - i - 1;
ans = ans + cnt * (cnt-1) / 2;
}
return s - ans;
}
double solve () {
s = (n-1) * (n-2) * (n-3) / 6.0;
double c = n * (n-1) * (n-2) / 6.0;
double ans = 0;
for (int i = 0; i < n; i++)
ans += Count(i);
return ans / c;
}
int main () {
int cas = 1;
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
printf("City %d: %.2lf\n", cas++, solve());
}
return 0;
}
分享到:
相关推荐
rate-constant-calculation-surpporting
Op-Amp-Noise-Calc-Sim-Meas-TG92309 全105页Op-Amp Noise Calculation and Measurement 运放噪声计算和测量 Art Kay Senior Applications Engineer Texas Instruments Inc –Tucson kay_art@ti.com
German Language - THERMOPLASTIC GEAR WHEELS - CYLINDRICALGEARS - CALCULATION 行业标准
资料-flyback transformer calculation.zip
Oracle Hyperion Chapter 3 - Rules and Calculation
FLUENT-UDF系统学习-Calculation of Flow Uniformity
GPS/COMPASS联合坐标计算。。。。
Configuration and the Calculation of Link Budget
igs观测数据文件处理,差分计算(c1-l1 c1-p1 c1-p2)
离散数学计算器 使用离散数学的公式对集合进行计数 控制台应用程序,用户可以在该应用程序上输入给定计数方法(排列,阶乘,组合)的值并获得结果
_C语言潮流计算程序,使用C语言编写,执行效率高,运行快。
本程序的功能是用牛顿——拉夫逊法进行10节点的潮流计算。
声品质的计算程序,各种参数的计算能够实现声音品质的预测和重构。
特殊函数计算的MATLAB例程,希望对学习MATLAB有用。
matlb实现电解常数的计算,有三种方法。
ANSI IES TM-34-19 Calculation Procedures and Specification Criteria for Lighting Calculations.pdf
7节点潮流运算的MATLAB程序,包括导纳、雅克比矩阵生成,运算结果输出等部分
根据经纬度计算椭球面子午圈半径、卯酉圈半径、纬圈半径、平行圈弧长以及梯形图幅面积。
基于MatlabGUI的电力系统短路计算:包括对称短路和不对称短路
实现信道容量的计算 用C语言编的,很不错,希望有帮助