번호 (0,0)

Question

첫째, 탑 코더 학점,이 문제가 자신의 SRM 중 하나에서 사용되었다 (그러나 그들이에 대한 편집이 없다 ..)로이 문제에

, 나는 n 점 (n은 1과 1000 사이)을 받았습니다. 세 점마다, 분명히 그들을 연결하는 삼각형이 있습니다. 문제는이 삼각형 중 몇 개가 점 (0,0)을 포함하고 있는가입니다. 내가 스택에이 스레드를보고 시도

:

triangle points around a point

하지만이 문제를 해결하기 위해 그들을 사용하는 방법/사용 어떤 데이터 구조를 이해 할 수없는입니다.

이 문제에 대한 명백한 순진한 해결책은 비효율적 인 O (n^3) 알고리즘을 사용하고 모든 점을 검색하는 것입니다. 그러나 누군가가 나를 더 효율적으로 만들 수 있도록 도와 주실 수 있습니까? O (n^2) 시간에이 작업을 수행 할 수 있습니까?

아래는이 문제에 대한 Petr의 해결책입니다 ... 매우 짧지 만 이해할 수없는 큰 아이디어가 있습니다.

/** 
* Built using CHelper plug-in 
* Actual solution is at the top 
*/ 
public class TrianglesContainOrigin { 
    public long count(int[] x, int[] y) { 
     int n = x.length; 
     long res = (long) n * (n - 1) * (n - 2)/6; 
     for (int i = 0; i < n; ++i) { 
      int x0 = x[i]; 
      int y0 = y[i]; 
      long cnt = 0; 
      for (int j = 0; j < n; ++j) { 
       int x1 = x[j]; 
       int y1 = y[j]; 
       if (x0 * y1 - y0 * x1 < 0) { 
        ++cnt; 
       } 
      } 
      res -= cnt * (cnt - 1)/2; 
     } 
     return res; 
    } 
} 

Answer 1

3 점 P1 = (X_1, y_1), P2 = (X_2, y_2)및 P3 = (x_3, y_3) 가진 삼각형이 될하자. p1, p2, p3를 위치 벡터라고합시다. 원점이있는 경우, 어느 한 위치 벡터와 다른 두 벡터의 교차 곱은 부호가 다릅니다 (하나는 음수, 하나는 양수). 그러나 원산지가 바깥에 놓여 있다면 다른 점들과 모두 음의 교차 곱을 갖는 하나의 점이 생길 것입니다. 따라서 각 점에 대해 십자가 곱이 0보다 작은 점을 찾습니다.이 점 중 두 점을 선택하고 점 i와 함께 삼각형을 만들면 원점은이 삼각형 외부에있게됩니다. 왜 당신이 res (2를 선택합니다. 그런 점에서 + 점 i). 이것은 double과 같은 정밀도의 문제가 없었으므로 많은 구현 된 최상의 솔루션이었습니다.