题解 P1355 【神秘大三角】

Mushroom_1965 · 2024-10-23 21:31:55 · 题解

一、前言

这是本蒟蒻写的第一篇题解，或许存在一定的不严谨甚至笔误之处，欢迎各位大佬指正。

写这篇题解是因为我判断点在三角形内还是在三角形外的方式没有在其他题解中看到，但也是一个对于此题而言的有效思路。

二、大伙都一样的部分

依次令输入的点为 A,B,C,D。

1、判断情况 4

直接枚举判断 D 是否与 A,B,C 中的任意一个重合。代码略。

2、判断情况 3

根据两向量共线的充要条件 \vec{a} = \lambda \vec{b} (\lambda \ne 0, \vec{b} \ne \vec{0}) ，我们容易推出：

在题目所给的条件下，即 \overrightarrow{PQ} \ne \vec{0} ，如果有点 O 在线段 PQ 上，那么就有：

，即：

，即：

三条线段每条都判断一次即可。意外地，题目数据中好像没出现过所有点 D 在某一条线段的延长线的的情况上，因为事后看了一下作者的AC代码发现作者没有考虑这一情况，这样理论上会WA掉点 O 在 QP 的延长线上的情况。

实际上，这里的判断条件中的所有大于等于和小于等于都对应改为大于小于也可，并且一旦做了这一改动，对情况 3 和情况 4 的判断就可以随意调换顺序。

三、和大伙不太一样的部分

根据平面向量三点共线定理：

若平面内有 O, A, B, C 四个点，且满足 \overrightarrow{OC} = \lambda \overrightarrow{OA} + \mu \overrightarrow{OB}，且 \lambda + \mu = 1，则 A, B, C 三点共线。

我们可以推出推论 1：

对于不共线向量 \overrightarrow{OA}, \overrightarrow{OB}，若 \overrightarrow{OC} = x \overrightarrow{OA} + y \overrightarrow{OB}，则

（1）点 C 在直线 AB 外侧（不含点 O 一侧）的充要条件是 x + y > 1；

（2）点 C 在直线 AB 内侧（含点 O 一侧）的充要条件是 x + y < 1。

证明可以问数学老师如下：

（1）必要性：如图，连 OC 交 AB 于点 C'，则存在实数 \lambda，使得 \overrightarrow{OC} = \lambda \overrightarrow{OC'}(\lambda > 1)，\overrightarrow{OC'} = x' \overrightarrow{OA} + y' \overrightarrow{OB}(x' + y' = 1)，\therefore \overrightarrow{OC} = \lambda x' \overrightarrow{OA} + \lambda y' \overrightarrow{OB}，x = \lambda x'，y = \lambda y'，\therefore x + y = \lambda (x' + y') > 1；
充分性：\because x + y > 1，\therefore \exist \lambda > 1，x = \lambda x'，y = \lambda y' 且 x' + y' = 1，\therefore \overrightarrow{OC} = \lambda (x' \overrightarrow{OA} + y' \overrightarrow{OB}) = \lambda \overrightarrow{OC'}，\because C' 在直线 AB 上，\therefore C 在直线 AB 外侧。

同理可证（2）。

以及推论 2：

若 \overrightarrow{OC} = x \overrightarrow{OA} + y \overrightarrow{OB}(x + y = 1, xy \ne 0)，则 \dfrac{|AC|}{|BC|} = \dfrac{|y|}{|x|}，且当 x > 0, y > 0，则点 C 在线段 AB 上。

证明去问数学老师吧略。

有了这两个推论，我们可以推知点 D 在 \triangle ABC 内的充要条件是：

即：

即：

于是我们只要算出 \lambda, \mu 然后判断是否满足条件，如果是则输出 1，否则通过输出 2。如何算出 \lambda, \mu ？我们可以夸张地使用高斯消元求得，这里不赘述高斯消元的做法了。

四、AC代码

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

const double eps = 1e-6;
double mat[3][4];
pair<int, int> a, b, c, d;
int main() {
    scanf("(%d,%d)\n", &a.first, &a.second);
    scanf("(%d,%d)\n", &b.first, &b.second);
    scanf("(%d,%d)\n", &c.first, &c.second);
    scanf("(%d,%d)\n", &d.first, &d.second);
    if ((d.first == a.first && d.second == a.second)
        || (d.first == b.first && d.second == b.second)
        || (d.first == c.first && d.first == c.second)) {
        cout << "4\n";
        return 0;
    }
    if (((a.second - b.second) * (a.first - d.first) == (a.second - d.second) * (a.first - b.first) && abs(a.second - b.second) > abs(a.second - d.second))    // 此处的判断理论有误，实际可以过本题，请读者自行修正
        || ((a.second - c.second) * (a.first - d.first) == (a.second - d.second) * (a.first - c.first) && abs(a.second - c.second) > abs(a.second - d.second))
        || ((b.second - c.second) * (b.first - d.first) == (b.second - d.second) * (b.first - c.first) && abs(b.second - c.second) > abs(b.second - d.second))) {
        cout << "3\n";
        return 0;
    }
    // 高斯消元
    mat[1][1] = b.first - a.first, mat[2][1] = b.second - a.second,
    mat[1][2] = c.first - a.first, mat[2][2] = c.second - a.second,
    mat[1][3] = d.first - a.first, mat[2][3] = d.second - a.second;
    int cnt = 0;
    for (int k = 1; k <= 2; k++) {
        int top = cnt + 1;
        for (int i = cnt + 2; i <= 2; i++) if (fabs(mat[i][k]) > fabs(mat[top][k]))
            top = i;
        if (fabs(mat[top][k]) <= eps) continue;
        for (int j = 1; j <= 3; j++) swap(mat[cnt + 1][j], mat[top][j]);
        for (int i = 1; i <= 2; i++) {
            if (i == cnt + 1) continue;
            double d = mat[i][k] / mat[cnt + 1][k];
            for (int j = k; j <= 3; j++) mat[i][j] -= mat[cnt + 1][j] * d;
        }
        ++cnt;
    }
    if (mat[1][3] / mat[1][1] > 0 && mat[2][3] / mat[2][2] > 0 && mat[1][3] / mat[1][1] + mat[2][3] / mat[2][2] < 1) {
        cout << "1\n";
        return 0;
    }
    cout << "2\n";
    return 0;
}