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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:51nod 1074 约瑟夫环 V2(约瑟夫环、模板)
下一篇:51nod 1112 KGold(优先队列)

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.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
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21
android gp服务,ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用) 2019-04-21
mysql整体会滚_滚mysql 2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据 2019-04-21
最全的mysql 5.7.13_最全的mysql 5.7.13 安装配置方法图文教程(linux) 强烈推荐! 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