CF1979E E. Manhattan Triangle题解

E. Manhattan Triangle

题目翻译

​ 题目给我们n个二维平面上的不同的点，我们要挑出三个点使得这三个点构成一个等边三角形边长为d（保证d是偶数），注意这里等边的边长意义是在曼哈顿距离下的。输出挑选哪三个点，无解输出0，0，0。

思路

​ 首先我们容易根据曼哈顿距离的定义发现对于某个点而言，距离它为d的点围成了一个菱形，同时因为三角形的性质，在曼哈顿意义下的等边三角形总有一条边是在斜率为1的线段上的（这里可以通过画图加以发现理解）。所以我们可以考虑枚举一个节点，然后考虑另外两个节点在斜率为1的线段上，我们x从小到大枚举，通过维护[x - d, x] 与 [x, x + d]的斜率为1或-1上的点来进行快速的判断是否存在我们当前点菱形四线段上间距为d的点对，这里只用考虑同一个线段上的点对即可，因为上面曼哈顿意义下等边的性质。具体维护我采用了map套set实现，标记线段归属的斜率和初相我使用x + y, x - y来进行标识。

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
void solve(){
    int n, d;
    std::cin >> n >> d;
    std::vector<std::pair<int, int>> cur(n + 1);
    std::map<std::pair<int, int>, int> ind;
    for(int i = 1; i <= n; i++){
        std::cin >> cur[i].ff >> cur[i].ss;
        ind[{cur[i].ff, cur[i].ss}] = i;
    }

    std::map<int, std::set<std::pair<int, int>>> shangx_d;    //记录从x-d到x的斜率为1的线段,存在距离为d的点对的情况
    std::map<int, std::set<std::pair<int, int>>> xiax_d;    //记录从x-d到x的斜率为-1的线段,存在距离为d的点对的情况
    std::map<int, std::set<std::pair<int, int>>> shangaddd; //记录从x到x + d的斜率为1的线段,存在距离为d的点对的情况
    std::map<int, std::set<std::pair<int, int>>> xiaaddd;   //记录从x到x + d的斜率为-1的线段,存在距离为d的点对的情况
    
    std::map<int, std::set<std::pair<int, int>>> shangx_dp;    //记录从x-d到x的斜率为1的线段,存在距离为d的点的情况
    std::map<int, std::set<std::pair<int, int>>> xiax_dp;    //记录从x-d到x的斜率为-1的线段,存在距离为d的点的情况
    std::map<int, std::set<std::pair<int, int>>> shangadddp; //记录从x到x + d的斜率为1的线段,存在距离为d的点的情况
    std::map<int, std::set<std::pair<int, int>>> xiaadddp;   //记录从x到x + d的斜率为-1的线段,存在距离为d的点的情况

    std::sort(cur.begin() + 1, cur.end());
    int left = 1;
    int right = 1;
    for(int i = 1; i <= n; i++){
        int x = cur[i].ff;
        int y = cur[i].ss;

        //右侧拓展
        while(right <= n && cur[right].ff <= x + d){
            int xn = cur[right].ff;
            int yn = cur[right].ss;
            shangadddp[xn - yn].insert({xn, yn});
            xiaadddp[xn + yn].insert({xn, yn});
            if(shangadddp[xn - yn].count({xn -  d / 2, yn - d / 2})){
                int minn = std::min(ind[{xn, yn}], ind[{xn - d / 2, yn - d / 2}]);
                int maxn = std::max(ind[{xn, yn}], ind[{xn - d / 2, yn - d / 2}]);
                shangaddd[xn - yn].insert({minn, maxn});
            }
            if(xiaadddp[xn + yn].count({xn - d / 2, yn + d / 2})){
                int minn = std::min(ind[{xn, yn}], ind[{xn - d / 2, yn + d / 2}]);
                int maxn = std::max(ind[{xn, yn}], ind[{xn - d / 2, yn + d / 2}]);
                xiaaddd[xn + yn].insert({minn, maxn});
            }
            right += 1;
        }

        //左侧删除
        while(left <= i && cur[left].ff < x - d){
            int xn = cur[left].ff;
            int yn = cur[left].ss;
            shangx_dp[xn - yn].erase({xn, yn});
            xiax_dp[xn + yn].erase({xn, yn});

            if(shangx_dp[xn - yn].count({xn + d / 2, yn + d / 2})){
                int minn = std::min(ind[{xn, yn}], ind[{xn + d / 2, yn + d / 2}]);
                int maxn = std::max(ind[{xn, yn}], ind[{xn + d / 2, yn + d / 2}]);  
                shangx_d[xn - yn].erase({minn, maxn});
            }

            if(xiax_dp[xn + yn].count({xn + d / 2, yn - d / 2})){
                int minn = std::min(ind[{xn, yn}], ind[{xn + d / 2, yn - d / 2}]);
                int maxn = std::max(ind[{xn, yn}], ind[{xn + d / 2, yn - d / 2}]);  
                xiax_d[xn + yn].erase({minn, maxn});
            }
            left += 1;
        }
        
        //左侧拓展
        shangx_dp[x - y].insert({x, y});
        xiax_dp[x + y].insert({x, y});
        if(shangx_dp[x - y].count({x -  d / 2, y - d / 2})){
            int minn = std::min(ind[{x, y}], ind[{x - d / 2, y - d / 2}]);
            int maxn = std::max(ind[{x, y}], ind[{x - d / 2, y - d / 2}]);
            shangx_d[x - y].insert({minn, maxn});
        }
        if(xiax_dp[x + y].count({x - d / 2, y + d / 2})){
            int minn = std::min(ind[{x, y}], ind[{x - d / 2, y + d / 2}]);
            int maxn = std::max(ind[{x, y}], ind[{x - d / 2, y + d / 2}]);
            xiax_d[x + y].insert({minn, maxn});
        }

        //获取是否存在匹配
        int needx = x + d;
        int needy = y;
        if(!shangaddd[needx - needy].empty()){
            auto p = *shangaddd[needx - needy].begin();
            std::cout << ind[{x, y}] << space << p.ff << space << p.ss << endl;
            return;
        }
        if(!xiaaddd[needx + needy].empty()){
            auto p = *xiaaddd[needx + needy].begin();
            std::cout << ind[{x, y}] << space << p.ff << space << p.ss << endl;
            return;
        }
        needx = x - d;
        needy = y;
        if(!shangx_d[needx - needy].empty()){
            auto p = *shangx_d[needx - needy].begin();
            std::cout << ind[{x, y}] << space << p.ff << space << p.ss << endl;
            return;
        }
        if(!xiax_d[needx + needy].empty()){
            auto p = *xiax_d[needx + needy].begin();
            std::cout << ind[{x, y}] << space << p.ff << space << p.ss << endl;
            return;
        }

        //右侧删除
        shangadddp[x - y].erase({x, y});
        xiaadddp[x + y].erase({x, y});
        if(shangadddp[x - y].count({x + d / 2, y + d / 2})){
            int minn = std::min(ind[{x, y}], ind[{x + d / 2, y + d / 2}]);
            int maxn = std::max(ind[{x, y}], ind[{x + d / 2, y + d / 2}]);
            shangaddd[x - y].erase({minn, maxn});
        }
        if(xiaadddp[x + y].count({x + d / 2, y - d / 2})){
            int minn = std::min(ind[{x, y}], ind[{x + d / 2, y - d / 2}]);
            int maxn = std::max(ind[{x, y}], ind[{x + d / 2, y - d / 2}]);
            xiaaddd[x + y].erase({minn, maxn});
        }
    }
    std::cout << 0 << space << 0 << space << 0 << endl;
}