NAIPC 2019 A - Piece of Cake(凸包计算)
2024-10-08 18:26:15
学习:https://blog.csdn.net/qq_21334057/article/details/99550805
题意:从nn个点中选择kk个点构成多边形,问期望面积。
题解:如果能够确定两个点,那么可以从这两个点之间选择k−2个点来构成一个k边形。所以可以枚举两个点,计算这两个点被选入构成凸包的概率和对凸包贡献的面积。
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef long double ld;
const int maxn = + ; struct Point {
ld x, y;
}a[maxn]; ld C[maxn][maxn]; void getC(int n) {
C[][] = ;
for (int i = ; i <= n; i++) {
C[i][] = ;
for (int j = ; j <= i; j++)
C[i][j] = C[i-][j] + C[i-][j-];
}
} ld Cross(Point a, Point b) {
return a.x*b.y - a.y*b.x;
} int n, k;
int main() {
ios::sync_with_stdio(false); cin >> n >> k;
getC(n); for (int i = ; i <= n; i++)
cin >> a[i].x >> a[i].y; ld ans = ;
for (int i = ; i <= n; i++)
for (int j = k-; j <= n-; j++) {
int t = i+j;
if (t > n) t -= n;
ans += Cross(a[i], a[t]) * C[j-][k-] / C[n][k];
} printf("%.7Lf\n", ans/);
}
最新文章
- Android基础总结(七)
- MYsql 数据库密码忘记(Linux)
- SQL Server 简介
- WPF的ComboBox 数据模板自定义
- 一、	Java的值传递和引用传递
- 【JAVA与DOM4J实现对XML文档的CRUD操作】
- (引用) unittest测试驱动之执行测试(三)
- 异步调用webservice
- 在Mapper中进行循环判断
- 响应式WEB设计
- 机器学习之python: kNN
- SignalR在Xamarin Android中的使用
- Python自然语言处理学习笔记之信息提取步骤&;分块(chunking)
- Vue事件处理
- Grunt针对静态文件的压缩,版本控制打包方案
- 点击table中的某一个td,获得这个tr的所有数据
- The 1st tip of DB Query Analyzer
- SQL Server 恢复数据库至指定时间点
- Asp.net Image控件显示Bitmap生成图像
- ElasticSearch(一):CentOS7 安装 ElasticSearch6.4.0
热门文章
- 1.3 this深度面试题
- .pcd格式点云文件的显示
- 反编译查看printf()的方法
- filter的原理(转)
- php魔术常量,_CLASS_,_METHOD_,_FUNCTION_
- UVALive 6491 You win! 状态DP
- 吴裕雄--天生自然 JAVASCRIPT开发学习: 验证 API
- 2020/1/28 PHP代码审计之代码执行漏洞
- 转载:微信小程序源码提取反编译
- Apache添加ssl支持