BOJ 13352 - 석양이 진다... 링크
(2023.08.17 기준 P4)

문제

맥크리가 새로운 무기와 총알 두발로 모든 적들을 없애려고 한다. 새로운 무기로 총알 한번 발사하면 직선상에 모든 적들을 없앨 수 있다.
맥크리는 구르는 속도가 아주 빨라서 순식간에 원하는 위치로 이동할 수 있다.

N명의 적의 위치가 주어질 때, 총알 두발로 모든 적들을 없앨 수 있는지 판별

알고리즘

CCW 및 무작위화

풀이

총알 한발을 쏘면 일직선 상의 모든 적들을 없앨 수 있고, 총알은 총 두발이다.
이 문제는 결국, 모든 적들이 두 개의 직선 위에 있는지 확인하는 문제이다.

BOJ 10523 - 직선 찾기 풀이와 굉장히 유사하다.
두 직선의 양 끝점이 될 네 점을 랜덤으로 뽑고, 모든 점들이 두 직선 중 최소 한 직선과 ccw 0을 이루는지 확인하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

// 난수 설정
random_device rd;
mt19937 generator(rd());

ll ccw(pll a, pll b, pll c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int randint(int l, int r){
    return uniform_int_distribution<int> (l, r)(generator);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 점의 개수가 4개 이하라면 무조건 가능하다.
    int N; cin >> N;
    if (N <= 4){
        cout << "success";
        return 0;
    }

    pll points[N];
    for (int i = 0; i < N; i++) cin >> points[i].x >> points[i].y;

    time_t st = time(0); // 시작 시간 체크
    while (true){

        // 두 직선의 양 끝점이 될 네 점을 무작위로 뽑는다.
        vector<pll> ends;
        while (ends.size() < 4){
            pll p = points[randint(0, N - 1)];
            if (find(ends.begin(), ends.end(), p) == ends.end()){
                ends.push_back(p);
            }
        }

        // 모든 점이 두 직선 중 최소 하나의 직선과 ccw가 0인지 확인
        bool is_possible = true;
        for (int i = 0; i < N; i++)
            if (ccw(ends[0], ends[1], points[i]) && ccw(ends[2], ends[3], points[i])){
                is_possible = false;
                break;
            }

        // 모든 점이 만족한다면 성공
        if (is_possible){
            cout << "success";
            break;
        }

        // 시작 시간으로부터 4초가 지났다면 불가능한 것으로 간주하고 종료
        if (time(0) - st > 4){
            cout << "failure";
            break;
        }
    }
}

• Python

import sys; input = sys.stdin.readline
from time import time
from random import randint

def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

# 점의 개수가 4개 이하라면 무조건 가능하다.
N = int(input())
if N <= 4:
    print('success')
    exit()

points = [tuple(map(int, input().split())) for _ in range(N)]

st = time() # 시작 시간 체크
while True:

    # 두 직선의 양 끝점이 될 네 점을 무작위로 뽑는다.
    ends = []
    while len(ends) < 4:
        p = points[randint(0, N - 1)]
        if p not in ends:
            ends.append(p)

    # 모든 점이 두 직선 중 최소 하나의 직선과 ccw가 0인지 확인
    for i in range(N):
        if ccw(ends[0], ends[1], points[i]) and ccw(ends[2], ends[3], points[i]):
            break
    else: # 모든 점이 만족한다면 성공
        print('success')
        break

    # 시작 시간으로부터 15초가 지났다면 불가능한 것으로 간주하고 종료
    if time() - st > 15:
        print('failure')
        break