[백준] 3042 트리플렛

알파벳 최대 26개가 들어올 때 3글자가 일직선인 것의 수를 찾는 문제다

진짜 직선만 완탐으로 다봤는데 바로 틀리더라

문제를 푸는 방법은 CCW 였다....!

잊고있었다 CCW..

점 3개를 줄 때 직선이면 0을 리턴하므로 그걸로 답을 세면 된다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
char arr[111][111];
vector<pair<int, int>> vt;
 
bool ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int ret = x1*y2 + x2*y3 + x3*y1;
    ret -= (y1*x2 + y2*x3 + y3*x1);
    if (!ret) return true;
    return false;
}
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf(" %1c", &arr[i][j]);
            if ('A' <= arr[i][j] && arr[i][j] <= 'Z') vt.push_back({ i,j });
        }
    }
    int m = vt.size();
    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++) {
                if (ccw(vt[i].first, vt[i].second, vt[j].first, vt[j].second, vt[k].first, vt[k].second)) ans++;
            }
        }
    }
    printf("%d\n", ans);
}