基准时间限制: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示例
4
2 3
3 4
1 5
4 6
Output示例
2
李陶冶 (题目提供者)
题目意思:
问你斜率小于0的两点的有多少个
问你斜率小于0的两点的有多少个
分析:
方法1:直接树状数组求解
这题跟poj 2352很相像
那题是求某个点左下角点的个数,本题是求某个点左上角点的个数
那题输入是由规则的(按照y的升序,y相等的话,x小的在前)
所以这题一开始也要按照这个规则先排一下序
如果我们直接求某个点左上角的点的个数的话,直接改一下那题就可以了,但是有一点麻烦的地方:
那个题处于做下角边界的情况也是统计在内的
但是这题不行
所以有点麻烦
但是我们可以转化一下思路
因为一开始按照那个排序规则是已经排好序了的
所以当前点肯定是y最大的点,那么以该点为分界点
和该点斜率大于等于0或者斜列不存在的点肯定都是位于该点的左下角的
那么这个时候所有点的数量(不包括当前点)减去当前点左下角的点的数量(包括左下角的边界)
就是斜率小于0的点的数量
即就是该点右下角点的数量(不包括边界的,边界的前面左下角算过了)
这题跟poj 2352很相像
那题是求某个点左下角点的个数,本题是求某个点左上角点的个数
那题输入是由规则的(按照y的升序,y相等的话,x小的在前)
所以这题一开始也要按照这个规则先排一下序
如果我们直接求某个点左上角的点的个数的话,直接改一下那题就可以了,但是有一点麻烦的地方:
那个题处于做下角边界的情况也是统计在内的
但是这题不行
所以有点麻烦
但是我们可以转化一下思路
因为一开始按照那个排序规则是已经排好序了的
所以当前点肯定是y最大的点,那么以该点为分界点
和该点斜率大于等于0或者斜列不存在的点肯定都是位于该点的左下角的
那么这个时候所有点的数量(不包括当前点)减去当前点左下角的点的数量(包括左下角的边界)
就是斜率小于0的点的数量
即就是该点右下角点的数量(不包括边界的,边界的前面左下角算过了)
还有一个问题就是数据太大了,c数组开不了,需要离散化
所以
先将输入的数据按照x离散化一下,因为每次getsum都是传x进去的
具体操作:
数据先按照x升序,x相等则y小的放前面的规则排序
因为每次getsum都是传x进去,所以按照x优先的规则排序好
排序好之后给按照顺序给点一个编号
这个就是所谓的离散化
然后getsum传进去的就是编号
具体理解一下,编号间的大小顺序关系和x原来的大小顺序关系是一样的
只是数据的范围被压缩了,但是期间各个数据的关系是没有变的
所以是可以这样的
这个就是离散化
所以
先将输入的数据按照x离散化一下,因为每次getsum都是传x进去的
具体操作:
数据先按照x升序,x相等则y小的放前面的规则排序
因为每次getsum都是传x进去,所以按照x优先的规则排序好
排序好之后给按照顺序给点一个编号
这个就是所谓的离散化
然后getsum传进去的就是编号
具体理解一下,编号间的大小顺序关系和x原来的大小顺序关系是一样的
只是数据的范围被压缩了,但是期间各个数据的关系是没有变的
所以是可以这样的
这个就是离散化
离散化完成之后
就是跟star那题差不多了,按照y升序,y相等则x小的放前面的规则排序
然后每次getsum的时候得到的是左下角点的数量
当前点总数(除当前点)减去当前点左下角点的数量
就是当前点右下角的数量
就是和当前点斜率小于0的点的数量
然后将每次getsum的答案加起来就是所有斜率小于0的点对的数量
就是跟star那题差不多了,按照y升序,y相等则x小的放前面的规则排序
然后每次getsum的时候得到的是左下角点的数量
当前点总数(除当前点)减去当前点左下角点的数量
就是当前点右下角的数量
就是和当前点斜率小于0的点的数量
然后将每次getsum的答案加起来就是所有斜率小于0的点对的数量
#include<queue>
#include<set>
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define max_v 500005
struct node
{
int x,y;
int num;
} p[max_v];
bool cmp1(node a,node b)//树状数组操作需要
{
if(a.y!=b.y)
return a.y<b.y;
else
return a.x<b.x;
}
bool cmp2(node a,node b)//离散化需要
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
int c[max_v];
int maxx;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
while(x<=maxx)
{
c[x]+=d;
x+=lowbit(x);
}
}
int getsum(int x,int num)
{
int res=;
while(x>)
{
res+=c[x];
x-=lowbit(x);
}
return num-res;//当前点总数减去该点左下角点的数量就是右下角点的数量
}
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(c,,sizeof(c));
for(int i=; i<n; i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
} //离散化
sort(p,p+n,cmp2);
int k=;
p[].num=k;
for(int i=; i<n; i++)
{
p[i].num=++k;
}
maxx=k; //树状数组
sort(p,p+n,cmp1);
long long ans=;
for(int i=; i<n; i++)
{
ans+=getsum(p[i].num,i);//注意是i,不是i+1,因为当前点总数不包括当前点自己
update(p[i].num,);
}
printf("%I64d\n",ans);
}
return ;
}
/*
题目意思:
问你斜率小于0的两点的有多少个 分析:
这题跟poj 2352很相像
那题是求某个点左下角点的个数,本题是求某个点左上角点的个数
那题输入是由规则的(按照y的升序,y相等的话,x小的在前)
所以这题一开始也要按照这个规则先排一下序
如果我们直接求某个点左上角的点的个数的话,直接改一下那题就可以了,但是有一点麻烦的地方:
那个题处于做下角边界的情况也是统计在内的
但是这题不行
所以有点麻烦
但是我们可以转化一下思路
因为一开始按照那个排序规则是已经排好序了的
所以当前点肯定是y最大的点,那么以该点为分界点
和该点斜率大于等于0或者斜列不存在的点肯定都是位于该点的左下角的
那么这个时候所有点的数量(不包括当前点)减去当前点左下角的点的数量(包括左下角的边界)
就是斜率小于0的点的数量
即就是该点右下角点的数量(不包括边界的,边界的前面左下角算过了) 还有一个问题就是数据太大了,c数组开不了,需要离散化
所以
先将输入的数据按照x离散化一下,因为每次getsum都是传x进去的
具体操作:
数据先按照x升序,x相等则y小的放前面的规则排序
因为每次getsum都是传x进去,所以按照x优先的规则排序好
排序好之后给按照顺序给点一个编号
这个就是所谓的离散化
然后getsum传进去的就是编号
具体理解一下,编号间的大小顺序关系和x原来的大小顺序关系是一样的
只是数据的范围被压缩了,但是期间各个数据的关系是没有变的
所以是可以这样的
这个就是离散化 离散化完成之后
就是跟star那题差不多了,按照y升序,y相等则x小的放前面的规则排序
然后每次getsum的时候得到的是左下角点的数量
当前点总数(除当前点)减去当前点左下角点的数量
就是当前点右下角的数量
就是和当前点斜率小于0的点的数量
然后将每次getsum的答案加起来就是所有斜率小于0的点对的数量 */
思路二:
转换为求逆序数,然后归并求逆序
从斜率的公式入手
(xi-xj)/(yi-yj)<0 的点对的个数
现在我们先按照x升序,x相同的则y小的放前面规则排好序
假设i<j
那么xi-xj肯定是小于0的
那么斜率要求小于0,则要求yi-yj大于0
则就是求排好序之后所有的y组成的序列的逆序数
它的逆序数就是斜率小于0点对的个数!
所以先按照那个规则排好序
然后将y拿出来组成一个数组
用归并排序求数列的逆序数
归并可以求逆序的理由:
(xi-xj)/(yi-yj)<0 的点对的个数
现在我们先按照x升序,x相同的则y小的放前面规则排好序
假设i<j
那么xi-xj肯定是小于0的
那么斜率要求小于0,则要求yi-yj大于0
则就是求排好序之后所有的y组成的序列的逆序数
它的逆序数就是斜率小于0点对的个数!
所以先按照那个规则排好序
然后将y拿出来组成一个数组
用归并排序求数列的逆序数
归并可以求逆序的理由:
在归并排序的过程中,比较关键的是通过递归,
将两个已经排好序的数组合并,
此时,若a[i] > a[j],则i到m之间的数都大于a[j],
合并时a[j]插到了a[i]之前,此时也就产生的m-i+1个逆序数,
而小于等于的情况并不会产生。
将两个已经排好序的数组合并,
此时,若a[i] > a[j],则i到m之间的数都大于a[j],
合并时a[j]插到了a[i]之前,此时也就产生的m-i+1个逆序数,
而小于等于的情况并不会产生。
#include<stdio.h>
#include<memory>
#include<algorithm>
using namespace std;
#define max_v 500005
typedef long long LL;
struct node
{
int x,y;
}p[max_v];
int a[max_v];
bool cmp(node a,node b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
int temp[max_v];
LL ans;
void mer(int s,int m,int t)
{
int i=s;
int j=m+;
int k=s;
while(i<=m&&j<=t)
{
if(a[i]<=a[j])
{
temp[k++]=a[i++];
}else
{
ans+=j-k;//求逆序数
temp[k++]=a[j++];
}
}
while(i<=m)
{
temp[k++]=a[i++];
}
while(j<=t)
{
temp[k++]=a[j++];
}
}
void cop(int s,int t)
{
for(int i=s;i<=t;i++)
a[i]=temp[i];
}
void megsort(int s,int t)
{
if(s<t)
{
int m=(s+t)/;
megsort(s,m);
megsort(m+,t);
mer(s,m,t);
cop(s,t);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==)
break;
ans=;
for(int i=;i<n;i++)
scanf("%d %d",&p[i].x,&p[i].y);
sort(p,p+n,cmp);
for(int i=;i<n;i++)
{
a[i]=p[i].y;
}
megsort(,n-);
printf("%lld\n",ans);
}
return ;
}
/*
从斜率的公式入手
(xi-xj)/(yi-yj)<0 的点对的个数
现在我们先按照x升序,x相同的则y小的放前面规则排好序
假设i<j
那么xi-xj肯定是小于0的
那么斜率要求小于0,则要求yi-yj大于0
则就是求排好序之后所有的y组成的序列的逆序数
它的逆序数就是斜率小于0点对的个数!
所以先按照那个规则排好序
然后将y拿出来组成一个数组
用归并排序求数列的逆序数
归并可以求逆序的理由: 在归并排序的过程中,比较关键的是通过递归,
将两个已经排好序的数组合并,
此时,若a[i] > a[j],则i到m之间的数都大于a[j],
合并时a[j]插到了a[i]之前,此时也就产生的m-i+1个逆序数,
而小于等于的情况并不会产生。 */