跳转至

CF598C

知识点

  • 计算几何
  • 极角排序

题意简述

给定 \(n\) 个向量的坐标表示 \(\mathbf{v}_i = (x, y)\),求任意两对向量的夹角的最小值所对应的那两个向量1

数据范围:\(1 \le n \le 10^5\)\(\left|x \right|, \left|y\right| \le 10^4\)\(x^2 + y^2 > 0\)

解题思路

首先考虑把所有的向量按照极角排序,但这也是有技巧的。

我们把整个坐标系分为 \(8\) 个部分:\(4\) 个象限和 \(4\) 个半坐标轴。

如果在同一个象限内,就很容易判断出极角的大小关系,否则就直接按照象限与象限之间的位置关系直接比较了。

注意 std::atan2(a, b) 的用法,它返回坐标表示为 \((b, a)\) 的向量的极角。

long double 枚举两个相邻的向量的极角差的大小即可。

代码实现

核心部分已用高亮标出。

Code
 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
#include <bits/stdc++.h>
#define LL long long

const long double PI = 3.1415926535897932384626;
const int N = 1e5 + 5;

int n, ansx, ansy;
long double ans = 1e9;

int quad(int x, int y) {
    if(x > 0 && y > 0) return 1;
    else if(x == 0 && y > 0) return 2;
    else if(x < 0 && y > 0) return 3;
    else if(x < 0 && y == 0) return 4;
    else if(x < 0 && y < 0) return 5;
    else if(x == 0 && y < 0) return 6;
    else if(x > 0 && y < 0) return 7;
    else if(x > 0 && y == 0) return 8;
} // 得到这个向量在哪个象限

struct POINT {
    int id, x, y;
    long double deg;
    bool operator<(const POINT &rhs) const {
        int quad1 = quad(x, y), quad2 = quad(rhs.x, rhs.y);
        if(quad1 != quad2)
            return quad1 < quad2;
        else
            return y * rhs.x < x * rhs.y; // 通过分五类讨论得到的通式
    }
} p[N];

int32_t main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d %d", &p[i].x, &p[i].y);
        p[i].id = i;
        p[i].deg = atan2(1.0 * p[i].y, 1.0 * p[i].x);
        if(p[i].deg < 0)
            p[i].deg += 2 * PI;
    }
    std::sort(p + 1, p + n + 1);
    p[0] = p[n];
    for(int i = 1; i <= n; ++i) {
        long double cur_ans = p[i].deg - p[i - 1].deg;
        if(cur_ans < 0)
            cur_ans += 2 * PI;
        if(cur_ans < ans) {
            ans = cur_ans;
            ansx = p[i].id, ansy = p[i - 1].id;
        }
    }
    printf("%d %d", ansx, ansy);
    return 0;
}

  1. 原题链接: C. Nearest vectors