51nod 1107 斜率小于0的连线数量(离散、树状数组)
发布日期:2021-11-02 09:48:34
浏览次数:1
分类:技术文章
本文共 1464 字,大约阅读时间需要 4 分钟。
1107 斜率小于0的连线数量
题目
二维平面上N个点之间共有C(n,2)条连线。求这C(n,2)条线中斜率小于0的线的数量。
二维平面上的一个点,根据对应的X Y坐标可以表示为(X,Y)。例如:(2,3) (3,4) (1,5) (4,6),其中(1,5)同(2,3)(3,4)的连线斜率 < 0,因此斜率小于0的连线数量为2。输入
第1行:1个数N,N为点的数量(0 <= N <= 50000)
第2 - N + 1行:N个点的坐标,坐标为整数。(0 <= X[i], Y[i] <= 10^9)输出
输出斜率小于0的连线的数量。(2,3) (2,4)以及(2,3) (3,3)这2种情况不统计在内。
输入样例
4
2 3 3 4 1 5 4 6输出样例
2
代码
将点按照x轴排序后,一次将点的y值离散后加入到树状数组中。
#include#define ll long longusing namespace std;int lowbit(int t) { return t & (-t);}struct node { int x, y; bool operator<(const node &a) const { return a.x > x; }} e[50006];int sum[50016];void add(int x) { for (int i = x; i; i -= lowbit(i)) sum[i]++;}int query(int x) { int ans = 0; for (int i = x; i < 50005; i += lowbit(i)) ans += sum[i]; return ans;}int n, a[50006], b[50006];int main() { cin >> n; for (int i = 1; i <= n; i++) { scanf("%d%d", &e[i].x, &e[i].y); a[i] = e[i].y; } sort(e + 1, e + n + 1); sort(a + 1, a + n + 1); int l = 1, r = 0; int ans = 0; e[0].x = -1; for (int i = 1; i <= n; i++) { if (e[i].x == e[i - 1].x) { r++; } else if (e[i].x != e[i - 1].x) { for (int j = l; j <= r; j++) { add(b[j]); } l = i; r = i; } b[i] = lower_bound(a + 1, a + n + 1, e[i].y) - a; ans += query(b[i] + 1); } printf("%d\n", ans); return 0;}
转载地址:https://blog.csdn.net/weixin_43820352/article/details/108186268 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月16日 17时14分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
h5引入json_纯js直接引入json文件
2019-04-21
python格式化字符串总结_Python字符串处理方法总结
2019-04-21
python中true什么意思_python中的bool是什么意思
2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例
2019-04-21
mysql整体会滚_滚mysql
2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据
2019-04-21
mssql连接mysql数据库文件_在本地 怎么远程连接MSSQL数据库
2019-04-21
mssql 远程无法连接mysql_解决SQLServer远程连接失败的问题
2021-06-24
linux mysql c++编程_Linux下进行MYSQL的C++编程起步手记
2021-06-24
Maria数据库怎么复制到mysql_MySQL、MariaDB数据库的AB复制配置过程
2021-06-24
mysql5.6 icp mrr bak_【mysql】关于ICP、MRR、BKA等特性
2021-06-24
mysql utf8跟utf8mb4_MySQL utf8 和 utf8mb4 的区别
2021-06-24
docker mysql开机自启动_Docker学习4-学会如何让容器开机自启服务【坑】
2019-04-21
在mysql中删除表正确的是什么_在MySQL中删除表的操作教程
2019-04-21
mysql有3个共同好友_共同好友mysql
2019-04-21
代理查询 mysql_查询数据库代理设置
2019-04-21