UVA378 题解

FurippuWRY · 2023-12-03 12:39:07 · 题解

非常好计算几何题。

本题前置知识：一次函数、直线方程等。

设两直线的解析式分别为 f(x)=y=k_1x+b_1,g(x)=y=k_2x+b_2，k_1 和 k_2 为斜率，b_1 和 b_2 为截距。

相交

若两直线相交，则它们的斜率肯定不相等，此时通过公式 k=\dfrac{y_1-y_2}{x_1-x_2} 可以求出两直线的斜率，b=y-kx，解方程求出 k 与 b。因为两直线有交点，所以此时 f(x)=g(x)，则有：

求出 x 之后，代入随便一个函数就能求出 y。

重合

若两直线重合，则它们的斜率与截距都相等，用上文两个公式求出后判定是否相等即可。

平行不重合

此时两直线的斜率相等，但截距不等。

特判

上文我们讨论的都是 x_1 \ne x_2 \land x_3 \ne x_4 的情况，但还存在 x_1=x_2 \land x_3 \ne x_4 等情况，此时如果无脑套公式，输出就会爆 nan，原因是 x_1-x_2=0，k=\dfrac{y_1-y_2}{x_1-x_2}=\dfrac{y_1-y_2}{0}，我们就要对于不同的 x 的值，进行分讨。

x_1=x_2 \land x_3 \ne x_4

此时两直线的斜率一定不等，存在交点 (x_1,g(x_1))。先求出 k_2 和 b_2，然后求出 g(x_1) 就行。

x_1 \ne x_2 \land x_3 = x_4

同理，交点为 (x_3,f(x_3))。

x_1 = x_2 \land x_3 = x_4

这种情况下，两直线的斜率都是无限大（相等），只存在平行和重合的两种情况，若 x_1=x_3，则为重合，否则为平行。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

double n, x[10], y[10];
double k1, k2, b1, b2, sol, solx, soly;

int main() {

    cin >> n;
    puts("INTERSECTING LINES OUTPUT");
    while (n--){
        for (ll i = 1; i <= 4; ++i) {
            cin >> x[i] >> y[i];
        }
        if (x[1] == x[2] && x[3] != x[4]) {
            k2 = (y[3] - y[4]) / (x[3] - x[4]);
            b2 = y[3] - x[3] * k2;
            solx = x[1];
            soly = solx * k2 + b2;
            printf("POINT %.2lf %.2lf\n", solx, soly);
        }
        else if (x[1] != x[2] && x[3] == x[4]){
            k1 = (y[1] - y[2]) / (x[1] - x[2]);
            b1 = y[1] - x[1] * k1;
            solx = x[3];
            soly = solx * k1 + b1;
            printf("POINT %.2lf %.2lf\n", solx, soly);
        }
        else if (x[1] == x[2] && x[3] == x[4]) {
            if (x[1] == x[3]) puts("LINE");
            else puts("NONE");
        }   
        else {
            k1 = (y[1] - y[2]) / (x[1] - x[2]);
            k2 = (y[3] - y[4]) / (x[3] - x[4]);
            b1 = y[1] - x[1] * k1;
            b2 = y[3] - x[3] * k2;
            if (b1 == b2 && k1 == k2) puts("LINE");
            else if (b1 != b2 && k1 == k2) puts("NONE");
            else {
                solx = (b1 - b2) / (k2 - k1);
                soly = solx * k1 + b1;
                printf("POINT %.2lf %.2lf\n", solx, soly);
            }
        }   
    }
    puts("END OF OUTPUT");

    return 0;
}