数据结构 邓俊辉 PA#1 灯塔(LightHouse) 题解

灯塔(LightHouse)


Description

As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input

1st line: N

2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).

Output

How many pairs of lighthourses can beacon each other

( For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same )

Example

Input

1
2
3
4
3
2 2
4 3
5 1

Output

1
1

Restrictions

For 90% test cases: 1 <= n <= 3 * 105

For 95% test cases: 1 <= n <= 106

For all test cases: 1 <= n <= 4 * 106

For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same.

1 <= x, y <= 10^8

Time: 2 sec

Memory: 256 MB

Hints

The range of int is usually [-231, 231 – 1], it may be too small.

描述

海上有许多灯塔,为过路船只照明。

(图一)

如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。

(图二)

若灯塔A、B均在对方的照亮范围内,则称它们能够照亮彼此。比如在图二的实例中,蓝、红灯塔可照亮彼此,蓝、绿灯塔则不是,红、绿灯塔也不是。

现在,对于任何一组给定的灯塔,请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。

第1行为1个整数n,表示灯塔的总数。

第2到n+1行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。

输出

1个整数,表示可照亮彼此的灯塔对的数量。

样例

见英文题面

限制

对于90%的测例:1 ≤ n ≤ 3×105

对于95%的测例:1 ≤ n ≤ 106

全部测例:1 ≤ n ≤ 4×106

灯塔的坐标x, y是整数,且不同灯塔的x, y坐标均互异

1 ≤ x, y ≤ 10^8

时间:2 sec

内存:256 MB

提示

注意机器中整型变量的范围,C/C++中的int类型通常被编译成32位整数,其范围为[-231, 231 – 1],不一定足够容纳本题的输出。

这道题其实和Openjudge 求排列的逆序数大同小异,那道题和这道题是一样的,都分成两个维度,前面那道题是数组的下标和数组的内容,而这道题则是x,y坐标,都是一样的道理,可是没看出来,后来参考别人的代码才有这种感觉。

贴代码:(这道题没有AC,95分,最后一个点数据范围太大TLE了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdlib>
using namespace std;
struct point{
    int x;
    int y;
};
void Merge(int *a,int s,int m,int e,int *b){
    int ptr1=s,ptr2=m+1,ptr=s;
    while (ptr1<=m&&ptr2<=e){
        if (a[ptr1]<a[ptr2]) b[ptr++]=a[ptr1++];
        else b[ptr++]=a[ptr2++];
    }
    while (ptr1<=m){
        b[ptr++]=a[ptr1++];
    }
    while (ptr2<=e){
        b[ptr++]=a[ptr2++];
    }
    for(int i=s;i<=e;i++){
        a[i]=b[i];
    }
}
long long getN(int *a,int s,int m,int e){
    long long re=0;
    int ptr1=s,ptr2=m+1;
    while(ptr1<=m&&ptr2<=e){
        if(a[ptr1]<a[ptr2]){
            re+=e-ptr2+1;
            ptr1++;
        }else{
            ptr2++;
        }
    }
    return re;
}
long long MergeSort(int *a,int s,int e,int *b){
    if(s<e){
        long long total=0;
        int m=s+(e-s)/2;
        total+=MergeSort(a,s,m,b);
        total+=MergeSort(a,m+1,e,b);
        total+=getN(a,s,m,e);
        Merge(a,s,m,e,b);
        return total;
    }
    return 0;
}
int cmp(const void * v1,const void *v2){
    return ((point *)v1)->x-((point *)v2)->x;
}
int main(){
    int n;
    cin>>n;
    point * arrayp=new point[n];
    for(int i=0;i<n;i++){
        cin>>arrayp[i].x>>arrayp[i].y;
    }
    qsort(arrayp,n,sizeof(point),cmp);
    int * array=new int[n];
    int * array2=new int[n];
    for(int i=0;i<n;i++){
        array[i]=arrayp[i].y;
    }
    long long re=MergeSort(array,0,n-1,array2);
    cout<<re;
    delete []arrayp;
    delete []array;
    delete []array2;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注