叉积

对于点 A,B,CA,B,C 其中 yA≥yBy_A\ge y_B，要判断一个点在直线的左侧还是右侧，可以通过向量 AC⃗,BC⃗\vec{AC},\vec{BC} 的叉积来判断，令 a⃗=AC⃗×BC⃗\vec{a}=\vec{AC}\times \vec{BC}，由右手法则可以得到，当 CC 在 ABAB 右侧时，a⃗\vec{a} 在 zz 轴的分量大于 00，左侧时小于 00，在直线上时等于 00。

因此，直接判断叉积在 zz 轴的分量与 00 的关系就可以判断点 CC 与直线 ABAB 的关系，下文直接用 AC⃗×BC⃗\vec{AC}\times\vec{BC} 代表其在 zz 轴的分量。

Toys

给定 nn 条线段将矩形分成 n+1n+1 个区域，并给 mm​ 个点 (xi,yi)(x_i,y_i)，求每个区域中有几个点，保证点不在线段上且在矩形内部。

数据范围：1≤n,m≤50001\le n,m\le 5000，−105≤xi,yi≤105-10^5\le x_i,y_i\le 10^5。

题目链接：POJ 2318。

对每个点二分出在它左边的最后一个直线，这样做是 O(mlog⁡n)O(m\log n)​ 的。为什么不用万能头？因为 POJ 不支持。

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
#include <cstdio>
using namespace std;

#define int long long
const int N = 5010;
int n, m, ans[N];

struct Vec {
    int x, y;

    int operator^(const Vec& v) {
        return x * v.y - y * v.x;
    }

    Vec operator-(const Vec& v) const {
        return {x - v.x, y - v.y};
    }
};

struct Line {
    Vec p[2];

    bool judge(Vec v) {
        return (v - p[0] ^ v - p[1]) > 0;
    }
} lines[N];

int solve(const Vec& p) {
    int l = 0, r = n;
    while (l < r) {
        int mid = (l+r+1) >> 1;
        if (lines[mid].judge(p)) l = mid;
        else r = mid - 1;
    }
    return r;
}

signed main() {
    int Y1, Y2, cnt = 0;
    while (scanf("%lld%lld%*d%lld%*d%lld", &n, &m, &Y1, &Y2), n) {
        if (cnt++) puts("");
        for (int i = 0; i <= n; i++) ans[i] = 0, lines[i].p[0].y = Y1, lines[i].p[1].y = Y2;
        for (int i = 1; i <= n; i++) scanf("%lld%lld", &lines[i].p[0].x, &lines[i].p[1].x);
        for (int i = 1, x, y; i <= m; i++) scanf("%lld%lld", &x, &y), ans[solve({x, y})]++;
        for (int i = 0; i <= n; i++) printf("%lld: %lld\n", i, ans[i]);
    }
    return 0;
}

Segments

给 nn 个线段，问是否存在一条直线满足所有线段在这条直线上的投影之间存在交点，如果 ∣a−b∣<10−8|a-b|< 10^{-8} 认为 a=ba=b。

数据范围：1≤n≤1001\le n\le 100​。

题目链接：POJ 3304。

如果存在这样一个点，它可以是某个线段投影的端点，所以考虑枚举端点，如果存在这样一条直线，那么这条线段的端点与它在这条直线上的投影之间的连线与所有线段相交，所以枚举端点作为直线经过的一个点，此时直线只有一个参数待定了。每经过一个线段都对这个直线的参数做出了一定约束，如果取到了约束的边界，一定是它碰到了另外一个线段的某个端点。

所以做法就是，枚举 (2n2)\binom{2n}{2} 个点对，确定一条直线，并且检查是否能包含住所有点，检查方式就是判断线段上两个点不在直线的同侧，转化为检查符号是否相同，并且当某个点在直线上是可以接受的，那么：

sgn(AC⃗×BC⃗)⋅sgn(AD⃗×BD⃗)>0\text{sgn}(\vec{AC}\times\vec{BC})\cdot \text{sgn}(\vec{AD}\times\vec{BD})> 0

这样复杂度是 O(n3)O(n^3) 的，可以通过。

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
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 110;
const double eps = 1e-8;
int n, T;

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

struct Vector {
    double x, y;

    double operator*(const Vector& v) const {
        return x * v.y - y * v.x;
    }

    Vector operator-(const Vector& v) const {
        return {x - v.x, y - v.y};
    }
    
    bool operator==(const Vector& v) const {
        return !sgn(x - v.x) && !sgn(y - v.y);
    }
} pnts[N*2], seg[N][2];

bool check(Vector a, Vector b) {
    if (a == b) return false;
    for (int i = 1; i <= n; i++) {
        int A = sgn((a - seg[i][0]) * (b - seg[i][0]));
        int B = sgn((a - seg[i][1]) * (b - seg[i][1]));
        if (A * B > 0) return false;
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        int k = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 1; j++, k++) {
                scanf("%lf%lf", &pnts[k].x, &pnts[k].y);
                seg[i][j] = pnts[k];
            }
        }
        
        for (int i = 1; i <= k; i++) {
            for (int j = i+1; j <= k; j++) {
                if (check(pnts[i], pnts[j])) {
                    puts("Yes!");
                    goto end;
                }
            }
        }

        puts("No!"); end:;
    }
    return 0;
}