🙇‍♀️[Silver I] 두 직선의 교차 여부 - 6487

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

기하학, 수학

제출 일자

2024년 6월 11일 14:33:03

문제 설명

두 개의 직선을 나타내는 4개의 점이 입력으로 주어질 때, 두 직선이 만나는지를 확인하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 N이 주어진다. (N <= 10)

다음 N개의 줄에는 각각 8개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어진다. 이는 두 직선 (x1, y1)-(x2, y2)와 (x3, y3)-(x4, y4)를 나타낸다.

(x1, y1)과 (x2, y2)는 서로 다른 점이며, (x3, y3)와 (x4, y4)는 서로 다른 점임이 보장된다.

모든 x와 y는 [-1000, 1000] 범위 내의 정수이다.

출력

각각의 테스트 케이스에 대해, 다음과 같이 출력한다.

  • 두 직선이 정확히 한 점에서 만난다면, POINT x y의 꼴로 출력한다. 이는 두 직선이 (x,y)에서 교차함을 의미한다. x와 y는 정확히 소숫점 아래 둘째 자리까지 출력한다.
  • 두 직선이 만나지 않는다면, NONE을 출력한다.
  • 두 직선이 무한히 많은 점에서 만난다면, LINE을 출력한다.

원문에 있는 INTERSECTING LINES OUTPUT/END OF OUTPUT 등은 출력하지 않는다.

🚀풀이

먼저 두 직선의 방정식을 구하고, 교점을 계산한다.
교차되는지 판별식을 통해 알아본다.
그 후, 평행 및 일치 여부를 확인한다.
소수점 둘째 자리까지 출력한다.

두 직선인데 두 선분으로 착각하고 선분 내에 존재하는지 체크하는 함수를 추가해서 문제를 풀었다.
그래서 한번 틀렸다.

또 소수점 둘째 자리까지 출력하는 경우, -0.00으로 출력되는 경우가 있어서 0.00으로 출력되게 만들었다.

image

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
#include <cmath>
#include <iomanip>

using namespace std;


// 두 직선의 방정식의 계수를 계산하는 함수
void getLineEquation(double x1, double y1, double x2, double y2, double& A, double& B, double& C) 
{
	A = y2 - y1;
	B = x1 - x2;
	C = A * x1 + B * y1;
}

// 두 선분이 교차하는지 확인하는 함수
bool onSegment(double x1, double y1, double x2, double y2, double x, double y) 
{
	return min(x1, x2) <= x && x <= max(x1, x2) && min(y1, y2) <= y && y <= max(y1, y2);
}

// 정밀한 출력을 위해 0.00과 -0.00을 구별하는 함수
double correctZero(double val) 
{
    return val == -0.00 ? 0.00 : val;
}

void solve()
{
    int N;
    cin >> N;

    cout << fixed << setprecision(2);

    while (N--) 
    {
        double x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

        double A1, B1, C1;
        getLineEquation(x1, y1, x2, y2, A1, B1, C1);
        double A2, B2, C2;
        getLineEquation(x3, y3, x4, y4, A2, B2, C2);

        double det = A1 * B2 - A2 * B1;

        if (det == 0) 
        {
            // 두 직선이 평행하거나 일치함을 확인
            if (A1 * x3 + B1 * y3 == C1) 
            {
                // 일치하는 경우
                cout << "LINE" << endl;
            }
            else 
            {
                // 평행한 경우
                cout << "NONE" << endl;
            }
        }
        else 
        {
            // 두 직선이 교차하는 경우
            double x = (B2 * C1 - B1 * C2) / det;
            double y = (A1 * C2 - A2 * C1) / det;

            x = correctZero(x);
            y = correctZero(y);

            cout << "POINT " << x << " " << y << endl;

            //if (onSegment(x1, y1, x2, y2, x, y) && onSegment(x3, y3, x4, y4, x, y)) 
            //{
            //    cout << "POINT " << x << " " << y << endl;
            //}
            //else 
            //{
            //    cout << "NONE" << endl;
            //}
        }
    }
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}

참고