首页 > 代码库 > 51NOD——N 1107 斜率小于0的连线数量
51NOD——N 1107 斜率小于0的连线数量
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注二维平面上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。
Input
第1行：1个数N，N为点的数量(0 <= N <= 50000)第2 - N + 1行：N个点的坐标，坐标为整数。(0 <= X[i], Y[i] <= 10^9)
Output
输出斜率小于0的连线的数量。(2,3) (2,4)以及(2,3) (3,3)这2种情况不统计在内。
Input示例
42 33 41 54 6
Output示例
2
先以x升序，y升序排序，然后给y离散化，求y的逆序对
和POJ star 差不多
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N(50000+5); 7 int n,maxn=1e9; 8 struct Node 9 {10 int x,y,mark;11 }node[N],use[N];12 bool cmp1(Node a,Node b)13 {14 if(a.x==b.x) return a.y<b.y;15 return a.x<b.x;16 }17 bool cmp2(Node a,Node b)18 {19 if(a.y==b.y) return a.mark<b.mark;20 return a.y<b.y;21 }22 23 #define LL long long24 #define lowbit(x) (x&((~x)+1))25 LL ans,t[N];26 void up(int x)27 {28 for(;x<=N+1;x+=lowbit(x)) t[x]++;29 }30 LL query(int x)31 {32 LL ret=0;33 for(;x;x-=lowbit(x)) ret+=t[x];34 return ret;35 }36 37 int main()38 {39 scanf("%d",&n);40 for(int i=1;i<=n;i++)41 {42 scanf("%d%d",&node[i].x,&node[i].y);43 node[i].x++; node[i].y++;;44 }45 sort(node+1,node+n+1,cmp1);46 for(int i=1;i<=n;i++) use[i].y=node[i].y,use[i].mark=i;47 sort(use+1,use+n+1,cmp2);48 for(int i=n;i>0;up(use[i--].mark))49 ans+=query(use[i].mark);50 printf("%lld\n",ans);51 return 0;52 }
51NOD——N 1107 斜率小于0的连线数量
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。