13352 - Target Practice

문제 링크

---

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

문제 요약

---

문제는 정말 간단하다. \(N\)개의 2차원 정수 좌표가 주어진다. 모든 좌표들이 최대 두개의 직선위에 놓일 수 있는가, 없는가를 판단하는 문제다.

문제 풀이

---

이 문제를 풀 수 있는 솔루션은 여러가지가 존재하지만 재미있는 방법 한가지를 소개하려 한다. 아래와 같은 프로그램을 상상해보자.

1. \(N\)개의 점중에 서로 다른 두 개의 점을 임의로 뽑자. 이 때 임의의 두 점을 이어 만든 직선을 \(A\)라고 하자.

2. 직선 \(A\)위에 존재하지 않는 점들이 새로운 직선 \(B\)위에 놓일 수 있는지 확인한다.

3. 만약 가능하다면 최대 두개의 직선으로 모든 좌표를 덮을 수 있다.

4. 만약 불가능 하다면 1번으로 돌아간다. 만약 반복횟수가 50번 이상을 넘어간다면 이는 불가능한 경우라고 판단한다.

위에서 말한 과정을 그대로 코드로 옮긴다면 억셉을 받을 수 있다. 아마 이러한 풀이를 처음 본다면 받아들이기 힘들 것이다. 하지만 이런 풀이가 왜 가능한지 한번 생각을 해보도록 하자.

우리가 생각해야 할 경우는 총 두가지다. 첫 번째 경우는 불가능한 경우이다. 이는 정당성을 증명할 필요가 없다. 불가능하다면 50번의 반복체크를 하는동안 성공을 할 이유가 없고 정상적으로 불가능하다고 판단을 할 것이기 때문이다. 그렇다면 실제 답이 가능할 경우이다. 이 때 직선 \(A\)가 \(n \above 1pt 2\)개의 좌표를 커버하고 있다고 가정을 해보자. 그렇다면 다른 직선 \(B\)가 커버하고 있는 점의 개수 또한 \(n \above 1pt 2\) 일것이다.

이 때 위에서 설명한 과정에서 실패할 확률이 어떻게 될까? 실패하는 경우는 직선 \(A\)위에 놓인 점에서 하나를 선택하고 직선 \(B\)위에 놓인 점 하나를 선택하는 경우이다. 이 때의 확률은 \(1 \above 1pt 4\)이다. 우리는 이러한 과정을 50번을 돌릴 것이다. 그렇다면 가능한  인풋임에도 불고하고 실패라고 답을 말할 확률은 \(({1 \above 1pt 4})^{50}\)이라 계산할 수 있다. 즉 가능한 경우임에도 불구하고 불가능하다고 말할 확률은 극악을 넘어 거의 일어나지 않는다고 봐도 무방하다.

물론 n이 3이하일 때, 또는 직선 한개로 모든 점을 커버할 수 있는경우는 따로 예외처리를 해주는 편이 안전하다.

소스 코드

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int INF = 987654321;
int n;
vector<pair<int, int>> vp;

int getGcd(int a, int b) {
  int x = a, y = b, z = a % b;
  while (z) {
    x = y;
    y = z;
    z = x % y;
  }
  return y;
}

pair<int, int> getSlope(int i, int j) {
  auto lo = vp[i], hi = vp[j];
  if (hi < lo) {
    swap(lo, hi);
  }
  int dx = hi.first - lo.first, dy = hi.second - lo.second;
  
  if (dx == 0) {
    return {0, INF};
  } else if (dy == 0) {
    return {INF, 0};
  } else {
    int gcd = getGcd(abs(dx), abs(dy));
    return {dx / gcd, dy / gcd};
  }
}

int main() {
  srand((unsigned)time(NULL));
  scanf("%d", &n);
  for (int i = 0 ; i < n ; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    vp.push_back({x, y});
  }
  
  if (n <= 3) {
    puts("success");
    return 0;
  }
  
  for (int iter = 0 ; iter < 50 ; ++iter) {
    int u, v;
    do {
      u = rand() % n;
      v = rand() % n;
    } while (u == v);
    
    pair<int, int> slope = getSlope(u, v);
    vector<int> left;
    for (int i = 0 ; i < n ; ++i) {
      if (i != u) {
        pair<int, int> comp = getSlope(u, i);
        if (comp != slope) {
          left.push_back(i);
        }
      }
    }
    
    if ((int)left.size() <= 1) {
      puts("success");
      return 0;
    }
    
    set<pair<int, int>> sp;
    for (int i = 1 ; i < (int)left.size() ; ++i) {
      pair<int, int> comp = getSlope(left[0], left[i]);
      sp.insert(comp);
    }
    
    if (sp.size() == 1) {
      puts("success");
      return 0;
    }
  }
  
  puts("failure");
}