부분합, CCW 판별

부분합과 CCW판별은 알고리즘 보다는 알고리즘 문제를 풀때의 테크닉 정도로 생각할 수 있다.

---

부분합.

배열의 연속된 부분의 합을 구할 때, 매번 그 구간의 합을 구한다면 굉장한 시간 낭비가 된다.

이럴때는 배열에 미리 0번지부터 i번지까지의 배열의 합을 미리 구해 놓으므로써

부분 합을 빠르게 구할 수 있다.

// // 배열 l 의 0~ n 의합을 sum에 저장해 놓는다. int sum[100]; sum[0] = 0; for( i=1; i<=n;i++){ sum[i] = sum[i-1] + l[i]; } i ~ j 까지의 합은 sum[j] - sum[i-1] 로 구할 수 있다.

---

CCW 판별.

CCW => Counter Clock Wise 의 줄인말이다. 2차원 좌표에서 세점이 존재할때 ( A, B, C ). 두점을 이은 선분을 긋는다( A -> B). 그 선분( A -> B, 방향이 A에서 B )을 기준으로  나머지 한점(C)이 시계방향에 있는지 시계 반대방향에 있는지 판별하는 것이다.

A -> B 방향으로 쭉 보았을때 왼쪽에 있는지 오른쪽에 있는 지.

그림으로 표현하면 

A 에서 B 점으로 향하는 선분에서 다음에 올 C나 D가 시계 방향인지 반시계 방향인지 확인 할 것이다.

이는 외적을 통해서 쉽게 알아 낼 수 있는데.

|  ax  bx  cx  |

|  ay  by  cy  |    

$$ (a{\tiny x} * b{\tiny y}) - (b{\tiny x} * a{\tiny y}) + ( b{\tiny x} * c{\tiny y} ) - ( c{\tiny x} * b{\tiny y} ) + ( c{\tiny x} * a{\tiny y} ) - ( a{\tiny x} * c{\tiny y} ) $$

$$ = (c{\tiny x} - a{\tiny x}) * (c{\tiny y} - b{\tiny y}) - (c{\tiny y} - a{\tiny y}) * (c{\tiny x} - b{\tiny x}) $$

이 결과 값이 양수인지 음수인지에 따라 CCW 인지 CW인지 를 판별 할 수 있다.

왜 외적을 하면 되는가 ? 이 값을 3점의 외적 보다 각 벡터의 외적으로 보는것이 편하다

$$ vector {\overline{AC}} = < (c{\tiny x} - a{\tiny x}),   (c{\tiny y} - a{\tiny y})>$$

$$ vector {\overline{BC}} = <(c{\tiny x} - b{\tiny x})  ,(c{\tiny y} - b{\tiny y})> $$

이렇게 보았을 때, CCW로 돌게되면 양수가 되고 ( 벡터의 외적시 오른손 법칙 참고 : https://ko.m.wikipedia.org/wiki/오른손_법칙 )

CW로 돌게되면 음수가 되고, 같은 직선상에 존재한다면 0이 된다. ( 같은 방향 벡터를 외적하면 0이된다. )