题意

世上最良心题目描述qwq

平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000

Sol

直接模拟是$n^3$的。

考虑先枚举一个$i$,那么我们要算的就是$\sum_{j = 1}^n \sum_{k = j + 1}^n |Cross((a_j, b_j), (a_k, b_k))|$

但是在计算相对坐标以及叉积的时候的时候会出现绝对值

前者我们在最开始按照$x$坐标排序,后者在枚举$i$时重新按照斜率从小到大排序

上面的式子可以化为

$$\sum_{j = 1}^n a_j \sum_{k = j + 1}^n b_k - b_j \sum_{k = j + 1}^n a_k$$

直接对$a,b$做后缀和即可

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = ;
int N;
struct Point {
int a, b;
Point operator - (const Point &rhs) const {
return (Point) {a - rhs.a, b - rhs.b};
}
bool operator < (const Point &rhs) const {
return a * rhs.b > rhs.a * b;
}
}p[MAXN], tmp[MAXN];
bool comp(const Point &aa, const Point &bb) {
return aa.a == bb.a ? aa.b < bb.b : aa.a < bb.a;
}
int main() {
N; scanf("%d", &N);
for(int i = ; i <= N; i++)
scanf("%lf %lf", &p[i].a, &p[i].b);
sort(p + , p + N + , comp);
memcpy(tmp, p , sizeof(p));
long double ans = ;
for(int i = ; i <= N; i++) {
for(int j = i + ; j <= N; j++) p[j] = p[j] - p[i];
sort(p + i + , p + N + );
double suma = , sumb = ;
for(int j = N; j > i; j--)
suma = suma + p[j + ].a, sumb = sumb + p[j + ].b,
ans = ans + p[j].a * sumb - p[j].b * suma;
memcpy(p, tmp, sizeof(tmp));
}
printf("%.1Lf", ans / );
return ;
}

最新文章

  1. oracle查询一个时间段每天的数据量
  2. 未能加载文件或程序集“AspNetPager”或它的某一个依赖项。参数错误(转)
  3. TWaver Flex开发示例及license下载
  4. PAT天梯赛练习题 L3-011. 直捣黄龙(多关键字SPFA+DFS)
  5. ORA-16019: cannot use LOG_ARCHIVE_DEST_1 with LOG_ARCHIVE_DEST or LOG_ARCHIVE_DUPLEX_DEST
  6. 提高CSS开发能力的技巧集
  7. 编写高质量代码改善java程序的151个建议——导航开篇
  8. ASP.NET Boilerplate 工作单元
  9. Problem B: 时间和日期类(III)
  10. mitm6:通过IPv6攻破IPv4网络
  11. Modbus总结
  12. c语言,数据结构,链表的一些操作总结
  13. Error:java: 无效的目标发行版: 1.8
  14. VUE插件大总结
  15. python 集成cython &amp;&amp; push 测试pip 仓库
  16. Keepalived+LVS-DR+Nginx高可用故障切换模式
  17. python 使用gevent模块实现手动挡切换多协程。
  18. python入门(五):切片列表元祖字典
  19. 多目标遗传算法 ------ NSGA-II (部分源码解析)目标函数 problemdef.c
  20. [转载]SQL中EXISTS的用法

热门文章

  1. spring cloud config 属性加解密
  2. POJ3621 Sightseeing Cows 最优比率环 二分法
  3. HTML&amp;CSS——background: url() no-repeat 0 -64px;CSS中背景图片定位方法
  4. 通过mysqldumpslow来分析日志
  5. 安装YouCompleteMe时,编译依赖的python版本不对
  6. SPOJ:NO GCD (求集合&amp;秒啊)
  7. NOIP提高组2006-金明的预算方案
  8. Java AWT组件开发和Swing界面编程
  9. ASP.NET Core MVC 2.x 全面教程_ASP.NET Core MVC 18. 基于Claim和Policy的授权 下 - 自定义Policy
  10. 任务49:Identity MVC:Model前端验证