취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13352번 문제인 석양이 진다...이다.
문제는 아래 링크를 확인하자.

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

각각의 적이 있는 좌표를 점이라 하자.

점이 4개 이하이면 두 점을 잇는 두 직선을 그어 모든 점이 두 직선 위에 올라가있게 할 수 있다. 또한, 모든 점이 두 직선 위에 올라가있을 수 있다면, 5개의 점 중 적어도 세 개의 점은 같은 직선 위에 있어야 한다.(비둘기집의 원리)

따라서 주어진 점이 5개 이상인 경우, 다섯 개의 점을 골라 점을 적어도 3개 포함하는 직선을 찾고(없다면 "failure" 출력), 그 직선 위에 있지 않은 모든 점이 한 직선 위에 있는지를 확인해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;

int gcd(int x, int y) {
    if (y) return gcd(y, x % y);
    return x;
}

int N, M;
int A[100000][2];
int pp = -1, qq = -1, rr = -1;
int visited[100000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    if (N <= 4) {
        cout << "success";
        return 0;
    }
    for (int i = 0; i < N; i++) cin >> A[i][0] >> A[i][1];
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < 5; j++) {
            for (int k = j + 1; k < 5; k++) {
                int dx1 = A[i][0] - A[j][0], dy1 = A[i][1] - A[j][1];
                int dx2 = A[j][0] - A[k][0], dy2 = A[j][1] - A[k][1];
                int g1 = gcd(abs(dx1), abs(dy1)), g2 = gcd(abs(dx2), abs(dy2));
                dx1 /= g1, dy1 /= g1, dx2 /= g2, dy2 /= g2;
                if (dx1 < 0) dx1 *= -1, dy1 *= -1;
                else if (!dx1) dy1 = 1;
                if (dx2 < 0) dx2 *= -1, dy2 *= -1;
                else if (!dx2) dy2 = 1;
                if (dx1 == dx2 && dy1 == dy2) {
                    pp = i, qq = j, rr = k;
                }
            }
        }
    }
    
    if (pp < 0) {
        cout << "failure";
        return 0;
    }
    
    visited[pp] = visited[qq] = 1;
    for (int k = 0; k < N; k++) {
        if (k == pp || k == qq) continue;
        int i = pp, j = qq;
        int dx1 = A[i][0] - A[j][0], dy1 = A[i][1] - A[j][1];
        int dx2 = A[j][0] - A[k][0], dy2 = A[j][1] - A[k][1];
        int g1 = gcd(abs(dx1), abs(dy1)), g2 = gcd(abs(dx2), abs(dy2));
        dx1 /= g1, dy1 /= g1, dx2 /= g2, dy2 /= g2;
        if (dx1 < 0) dx1 *= -1, dy1 *= -1;
        else if (!dx1) dy1 = 1;
        if (dx2 < 0) dx2 *= -1, dy2 *= -1;
        else if (!dx2) dy2 = 1;
        if (dx1 == dx2 && dy1 == dy2) visited[k] = 1;
    }
    
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            A[M][0] = A[i][0], A[M][1] = A[i][1];
            M++;
        }
    }
    
    for (int j = 1; j + 1 < M; j++) {
        int i = j - 1, k = j + 1;
        int dx1 = A[i][0] - A[j][0], dy1 = A[i][1] - A[j][1];
        int dx2 = A[j][0] - A[k][0], dy2 = A[j][1] - A[k][1];
        int g1 = gcd(abs(dx1), abs(dy1)), g2 = gcd(abs(dx2), abs(dy2));
        dx1 /= g1, dy1 /= g1, dx2 /= g2, dy2 /= g2;
        if (dx1 < 0) dx1 *= -1, dy1 *= -1;
        else if (!dx1) dy1 = 1;
        if (dx2 < 0) dx2 *= -1, dy2 *= -1;
        else if (!dx2) dy2 = 1;
        if (dx1 != dx2 || dy1 != dy2) {
            cout << "failure";
            return 0;
        }
    }
    
    cout << "success";
}