HDU3629：Convex

古城微笑少年丶 2021-12-23 07:53 108阅读 0赞

[传送门][Link 1]  
求凸四边形的个数  
转化成总数减去凹四边形的个数  
凹四边形一定是一个三角形中间包含的另外一个点  
那么枚举被包含的点，其它的对于这个点极角排序  
被包含不好算，算总数减去不被包含的  
枚举三角形的一个顶点，那么另外一个顶点和这个顶点关于枚举的被包含的点的角度不超过 \\(\\pi\\)  
那么直接 \\(two-pointers\\) 统计即可

# include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn(2005); const double eps(1e-9); const double pi(acos(-1)); int n, test, tot; ll ans, ret; struct Point { int x, y; double angle; inline bool operator <(Point b) const { return angle - eps < b.angle; } } a[maxn], b[maxn]; inline ll Calc(int p) { register int i, j; ret = (ll)(n - 1) * (n - 2) * (n - 3) / 6, tot = 0; for (i = 1; i <= n; ++i) if (i ^ p) { ++tot, b[tot].x = a[i].x - a[p].x, b[tot].y = a[i].y - a[p].y; b[tot].angle = atan2(b[tot].y, b[tot].x); b[tot + n - 1].angle = b[tot].angle + pi * 2; } tot += n - 1, sort(b + 1, b + tot + 1); for (i = 1, j = 1; i < n; ++i) { while (j < i + n - 1 && b[j].angle - b[i].angle - eps < pi) ++j; if (j - i - 1 >= 2) ret -= (ll)(j - i - 1) * (j - i - 2) / 2; } return ret; } int main() { register int i; scanf("%d", &test); while (test) { scanf("%d", &n), --test; for (i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y); ans = (ll)n * (n - 1) * (n - 2) * (n - 3) / 24; for (i = 1; i <= n; ++i) ans -= Calc(i); printf("%lld\n", ans); } return 0; }

转载于:https://www.cnblogs.com/cjoieryl/p/10206379.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3629

发表评论取消回复

表情：

评论列表（有 0 条评论，108人围观）

还没有评论，来说两句吧...

相关阅读

相关 UltraISO 9.7.3.3629下载及安装步骤

文章目录 1. 按 2. 下载 3. 安装步骤 1. 按 UltraISO软碟通是一款功能强大、方便实用、老牌优秀的光盘映像文件制作/编辑/转换

桃扇骨/ 2023年02月20日 08:23/ 0 赞/ 70 阅读

相关 hdu 2112 ——HDU Today

Problem Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发

朴灿烈づ我的快乐病毒、/ 2022年08月09日 13:46/ 0 赞/ 183 阅读

相关 HDU - 2112 - HDU Today

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=2112][http_acm.hdu

布满荆棘的人生/ 2022年06月12日 10:40/ 0 赞/ 180 阅读

相关 kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_sh

叁歲伎倆/ 2022年05月14日 11:24/ 0 赞/ 178 阅读

相关 OpenCV入门之寻找图像的凸包（convex hull）

介绍凸包(Convex Hull)是一个计算几何（图形学）中的概念，它的严格的数学定义为：在一个向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包

心已赠人/ 2022年05月09日 03:33/ 0 赞/ 293 阅读

相关凸包（Convex Hull）

凸包介绍 -------------------- 代码 include <opencv2/opencv.hpp> include <i

柔情只为你懂/ 2022年03月22日 09:42/ 0 赞/ 314 阅读

相关 HDU3629：Convex

[传送门][Link 1] 求凸四边形的个数转化成总数减去凹四边形的个数凹四边形一定是一个三角形中间包含的另外一个点那么枚举被包含的点，其它的对于这个点极

古城微笑少年丶/ 2021年12月23日 07:53/ 0 赞/ 109 阅读

相关 LOJ#6504. 「雅礼集训 2018 Day5」Convex（回滚莫队）

题面 [传送门][Link 1] 题解因为并不强制在线，我们可以考虑莫队然而莫队的时候有个问题，删除很简单，除去它和前驱后继的贡献即可。但是插入的话却要找到

今天药忘吃喽~/ 2021年12月23日 05:45/ 0 赞/ 207 阅读

相关 POJ 3629 队列模拟

听说STL会卡T 然后我就试了一发哈哈哈哈哈哈哈哈哈哈 1000ms卡时过的这很值得我写一发题解了哈哈哈哈哈哈哈哈哈哈哈哈 //By SiriusRen

Myth丶恋晨/ 2021年12月22日 14:17/ 0 赞/ 215 阅读

相关 P3629 【[APIO2010]巡逻】

今天在机房里考了这题。。。。。lbw巨佬一下考场就开始大喊“第二题把直径赋为-1再跑一次直径就行”，作为一个蒟蒻也没有啥好说的，自己弱，没办法。下午再想这道题，忽然有个暴力的

叁歲伎倆/ 2021年11月17日 21:54/ 0 赞/ 216 阅读