BZOJ1132: [POI2008]Tro(叉积 排序)
2018-07-27 06:10:29来源:博客园 阅读 ()
题意
世上最良心题目描述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 = 3001; 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 = 1; i <= N; i++) scanf("%lf %lf", &p[i].a, &p[i].b); sort(p + 1, p + N + 1, comp); memcpy(tmp, p , sizeof(p)); long double ans = 0; for(int i = 1; i <= N; i++) { for(int j = i + 1; j <= N; j++) p[j] = p[j] - p[i]; sort(p + i + 1, p + N + 1); double suma = 0, sumb = 0; for(int j = N; j > i; j--) suma = suma + p[j + 1].a, sumb = sumb + p[j + 1].b, ans = ans + p[j].a * sumb - p[j].b * suma; memcpy(p, tmp, sizeof(tmp)); } printf("%.1Lf", ans / 2); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:洛谷P2742 【模板】二维凸包
下一篇:char string 区别
- 割点 2019-08-26
- Devexpress之GridControl显示序列号 2018-06-27
- MFC 中的 Value 和 Control 2018-06-18
- c# GridControl怎么换行 2018-06-18
- 用户控件的设计要点 System.Windows.Forms.UserControl 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash