6487번: 두 직선의 교차 여부

https://www.acmicpc.net/problem/6487


$O(n)$

두 직선의 기울기가 다르면 교점을 구하고 같다면 같은 직선이었는지 판별한다.
교점을 구할 때 벡터를 사용하면 편하다.
a,b,c,d를 아래 소스처럼 놓으면
교점 P=(ar+x[0],br+y[0])=(cs+x[2],ds+y[2])
를 만족하는 r,s를 구하면 된다.

#include<cstdio>
int n, x[4], y[4];
int main() {
    for (scanf("%d", &n); n--;) {
        for (int i = 0; i < 4; i++) scanf("%d%d", x + i, y + i);
        double a = x[1] - x[0], b = y[1] - y[0], c = x[3] - x[2], d = y[3] - y[2];
        if (a*d - b*c) {
            double r = (d*(x[2] - x[0]) - c*(y[2] - y[0])) / (a*d - b*c);
            printf("POINT %.2lf %.2lf\n", a*r + x[0], b*r + y[0]);
        }
        else puts((x[2] - x[0])*b - (y[2] - y[0])*a ? "NONE" : "LINE");
    }
    return 0;
}