[BOJ] 3042번: 트리플렛

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

이전 포스트가 CCW였는데 사실 이 문제를 풀기 위해 복습한 것이었다. CCW를 안다면 상당히 쉽게 풀 수 있는 문제였다.

핵심은 ccw이긴 해도 좌표만 따로 저장하는 것도 나름의 스킬인 것 같다. 그러면 더 쉬우니까...

그래서 알파벳들이 있는 x, y 좌표를 3개 잡고 ccw를 확인해서 그 값이 0이면 기록을 증가시키면 된다!

#include <cstdio>

int n;
char A[100][101];

int x[26], y[26], m;

int CCW(int x1, int y1, int x2, int y2, int x3, int y3)
{
    int temp = x1 * y2 + x2 * y3 + x3 * y1;
    temp -= (x2 * y1 + x3 * y2 + x1 * y3);
    if (temp > 0)
        return 1;
    else if (temp < 0)
        return -1;
    return 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", A[i]);
        for (int j = 0; j < n; ++j)
            if (A[i][j] != '.')
            {
                x[m] = i;
                y[m] = j;
                m++;
            }
    }

    int ans = 0;

    for (int i = 0; i < m; ++i)
        for (int j = i + 1; j < m; ++j)
            for (int k = j + 1; k < m; ++k)
            {
                int retCCW = CCW(x[i], y[i], x[j], y[j], x[k], y[k]);
                if (retCCW == 0)
                    ans++;
            }
    printf("%d\n", ans);
    return 0;
}