[C/C++] 프로젝트 오일러 #102 Triangle Containment(수학)

프로젝트 오일러 문제 #102, “Triangle Containment”은 기하학과 좌표를 활용한 문제로, 수학적 사고와 프로그래밍 기술을 결합하여 해결해야 하는 문제입니다. 난이도는 15%로 평가되고 있으며, 특히 2D 좌표평면에서 삼각형과 점의 관계를 다루는 문제를 즐기는 이들에게 적합합니다.

이 문제의 기본적인 목표는 주어진 수많은 삼각형들 중에서 원점(0, 0)이 포함된 삼각형의 개수를 찾는 것입니다. 각 삼각형은 세 점의 좌표로 표현되며, 파일에 저장된 데이터를 읽어와 이를 처리해야 합니다. 원점이 특정 삼각형 내부에 포함되어 있는지를 확인하기 위해서는 벡터와 내적, 교차곱 등의 기하학적 개념을 활용하거나, 삼각형의 넓이를 비교하는 방식 등 다양한 접근법을 사용할 수 있습니다.

이 문제는 단순히 원점을 포함하는 삼각형의 개수를 찾는 작업을 넘어서, 수학적 기하학과 알고리즘 설계 능력을 테스트합니다. 이를 해결하기 위해서는 삼각형의 각 점과 원점 간의 관계를 계산적으로 정의하고, 수백 개 이상의 삼각형에 대해 효율적으로 판별하는 방법을 설계해야 합니다. 특히, 문제의 데이터를 읽고 파싱하는 과정도 해결의 중요한 일부로 포함됩니다.

triangle containment

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #102 - Triangle Containment
//        - by Aubrey Choi
//        - created at 2015-10-27
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    FILENAME    "0102.txt"

bool CheckOrigin(int a[][2])
{
    bool s = (a[0][0]*a[1][1] - a[1][0]*a[0][1]) > 0;
    bool k = (a[1][0]*a[2][1] - a[2][0]*a[1][1]) > 0;
    if( k != s ) return false;
    k = (a[2][0]*a[0][1] - a[0][0]*a[2][1]) > 0;
    return k == s;
}

void solve1()
{
    FILE *fi = fopen(FILENAME, "r");

    int count = 0;
    while( true )
    {
        char str[1000];
        if( fgets(str, 1000, fi) == NULL ) break;
        int tri[3][2];
        sscanf(str, "%d,%d,%d,%d,%d,%d", &tri[0][0], &tri[0][1], &tri[1][0], &tri[1][1], &tri[2][0], &tri[2][1]);
        if( CheckOrigin(tri) ) count++;
    }
    fclose(fi);

    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

문제의 목표는 주어진 삼각형 좌표들 중 원점(0, 0)을 내부에 포함하고 있는 삼각형의 개수를 계산하는 것입니다.

1. 파일 입력 처리:
• 삼각형의 좌표는 0102.txt 파일에 저장되어 있습니다. 각 줄은 6개의 정수로 구성되어 있으며, 각각 삼각형을 이루는 세 꼭짓점의 (x, y) 좌표를 나타냅니다.
• 프로그램은 파일을 읽으면서 각 줄의 데이터를 파싱하여 삼각형의 좌표를 배열에 저장합니다.

 

2. 삼각형의 내부 여부 판별:
• 원점이 삼각형 내부에 포함되는지 확인하기 위해 벡터의 외적을 사용합니다.
• CheckOrigin 함수는 삼각형의 세 점을 기준으로 각 변에서 원점의 위치를 계산하고, 원점이 삼각형 내부에 존재하는지를 판단합니다.
• 외적 값을 기준으로 삼각형의 각 꼭짓점에 대해 원점이 같은 방향에 있는지 비교하며, 만약 세 변에서 동일한 방향에 위치하면 원점은 삼각형 내부에 포함된 것으로 간주합니다.

 

1. CheckOrigin 함수:

bool CheckOrigin(int a[][2])
{
    bool s = (a[0][0]*a[1][1] - a[1][0]*a[0][1]) > 0;
    bool k = (a[1][0]*a[2][1] - a[2][0]*a[1][1]) > 0;
    if( k != s ) return false;
    k = (a[2][0]*a[0][1] - a[0][0]*a[2][1]) > 0;
    return k == s;
}

• 삼각형 꼭짓점의 좌표 배열 a[3][2]을 받아 원점이 내부에 있는지 확인합니다.
• 각 변에 대해 외적 값을 계산하여 원점이 동일한 방향에 있는지를 비교합니다.
• 외적 값의 부호가 동일하지 않으면 원점은 삼각형 외부에 있습니다. 모든 외적 값의 부호가 동일하면 true를 반환합니다.

2. solve1 함수:

void solve1()
{
    FILE *fi = fopen(FILENAME, "r");

    int count = 0;
    while( true )
    {
        char str[1000];
        if( fgets(str, 1000, fi) == NULL ) break;
        int tri[3][2];
        sscanf(str, "%d,%d,%d,%d,%d,%d", &tri[0][0], &tri[0][1], &tri[1][0], &tri[1][1], &tri[2][0], &tri[2][1]);
        if( CheckOrigin(tri) ) count++;
    }
    fclose(fi);

    printf("Ans = %d\n", count);
}

• 입력 파일을 열어 한 줄씩 읽고, 각 줄에서 삼각형의 좌표를 추출합니다.
• 삼각형의 좌표를 tri 배열에 저장한 후, CheckOrigin 함수를 호출해 원점이 포함되었는지 확인합니다.
• 원점을 포함하는 삼각형의 개수를 count로 누적한 후 결과를 출력합니다.

3. main 함수:

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

• 프로그램 시작 시 시간을 기록하고, solve1 함수를 호출하여 문제를 해결합니다.
• 프로그램이 끝난 뒤 경과 시간을 계산하여 출력합니다.

주요 개념 및 코드의 장점

1. 벡터 외적 활용:
• 삼각형 내부 여부를 판단하는 데 외적을 사용한 것은 간단하면서도 효율적인 접근 방식입니다.
• 세 변에 대해 동일한 부호의 외적 값을 확인하는 방법은 수학적으로 타당하며 계산량이 적습니다.

 

2. 파일 입력 처리:
• 삼각형 좌표를 간단하게 읽고 처리할 수 있도록 구현되어 있으며, 포맷이 일관된 경우 문제없이 작동합니다.

 

3. 성능 최적화:
• 각 삼각형에 대해 외적만 계산하므로 시간 복잡도가 낮고, 파일 읽기와 처리 과정이 효율적입니다.
• 경과 시간을 출력하는 기능은 성능 측정에 유용합니다.