필수로 알아야할 내용
1. 사선 정리 : 다각형 면적, 각도 방향성(CCW,CW,직선) 판별 --> 외적과 동일
2. 내적(직각여부, 투영), 외적(면적, 각도방향성)
3. 점과 직선 사잇거리
4. 라인 교차
5. 내/외부 판별
6. convex hull
---------------
1. 사선 정리
세 점 P(x1,y1), A(x2,y2), B(x3,y3)가 있을 때, 삼각형 APB의 면적은? 각 APB의 방향은?
S=1/2 * (x1y2+x2y3+x3y1-x2y1-x3y2-x1y3)
S의 부호를 가지고 각도의 방향이 CCW(반시계방향)이지 CW(시계방향)인지를 판가름하는 것은, 두 벡터의 외적을 가지고 각도의 방향을 판가름 하는 것으로부터 유도 가능.
즉, 방향 = ((A-P) x (B-P)) > 0 ? CCW : CW
사선공식은 세 점이 아닌 n개의 점으로 이루어진 다각형의 합에도 동일하게 이용 가능
2. 내적, 외적
A(x1,y1), B(x2,y2)에 대해서,
내적: A dot B = x1x2 + y1y2 = |A| |B| cos(s) //s는 A와 B 사잇각
외적: A x B = x1y2 - x2y1
*내적의 활용
- 두 벡터의 직각 여부: if(A dot B == 0) then OA 와 OB는 직각.
왜냐하면 s = acos[(A dot B) / |A| |B|] 이기에, A dot B가 0이면 s는 90도 혹은 270도(시계방향으로 직각)
- 다른 벡터로의 투영(projection)
B의 단위벡터를 r이라 했을 때,
r = (x2/|B|, y2/|B|)
A와 r의 내적은,
A dot r = |A| cos(s) (왜냐면 |r|=1 )
A의 B로의 투영한 길이는 |A| cos(s)이므로, 투영한 벡터는 단위벡터 r을 이 길이만큼 늘린 것.
따라서,
투영벡터 = r * (A dot r) = r * (|A| cos(s))
* 외적의 활용
- 면적: 두 벡터의 외적은, 두 벡터를 가지고 만들어지는 평행사변형의 면적. 따라서, 1/2을 하면 삼각형의 면적(사선공식과 동일)
- 방향:
A x B > 0 ==> A를 기준으로 해서, B가 왼쪽에 있음(CCW)
< 0 ==> CW
= 0 ==> 직선
3. 점과 직선 사잇거리
점P에서 직선AB사잇 거리
- P를 AB에 투영한 벡터 Q를 구한다.
벡터 (B-A)의 단위벡터를 r이라 하면,
Q = r * (P dot r)
- 거리는 |P-Q|
4. 라인 교차 여부
- 두 선분(네 점)이 주어졌을 때, 교차여부 판단. : a, b, c, d
--> 선분 ab를 기준으로 c와 d가, 선분 cd를 기준으로 a, b가 각기 다른 방향에 있는 지 확인
struct P {
int x, y;
P() {}
P(int _x, int _y) { x = _x; y = _y; }
P operator - (P& rhs) const { return P(x-rhs.x, y-rhs.y);}
bool operator < (P& rhs) { return (x != rhs.x) ? (x < rhs.x) : (y < rhs.y); }
};
int cross(P a, P b) { return a.x * b.y - a.y*b.x; }
int ccw(P a, P b, P c) {return cross(b - a, c - a);}
bool isInter(P a, P b, P c, P d) {
int ab = ccw(a, b, c) * ccw(a, b, d);
int cd = ccw(c, d, a) * ccw(c, d, b);
if (ab == 0 && cd == 0) {
if (b < a) swap(a, b);
if (d < c) swap(c, d);
// [a..b]인 경우만 true. 즉, !( d<- a~b -> c )
return !(d<a || b<c);
}
return ab <= 0 && cd <= 0;
}
5. 내/외부 판별
- 여러 점들로 이루어진 다각형(볼록, 오목 상관없음)이 있을 때, 어떤 한 점이 이 다각형의 내부에 있는 지 외부에 있는 지를 판별.
- 기본 원리는, 그 점에서 오른쪽 방향으로 선을 그었을 때 다각형의 선분과 홀수번 만나는 지, 짝수번 만나는 지를 파악하는 것.
홀수번: 내부, 짝수번: 외부
- 이 때 주의할 것은, 아래 그림과 같은 케이스들에 대해서, 그림에서 카운팅된 것처럼 제대로 카운팅되야 하는 것
이를 위해서는 라인에 대해서, 밑에 점과 위에 점 중에서, 어느하나만 카운트 되야하고, 만약 평행하다면 하나도 카운트 되지 말아야 함.
이렇게 하도록 하는 것이 아래 코드.
if( (p[i].y > q.y) != (p[j].y > q.y))
이것을 p[i].y=y1, p[j].y=y2, q.y=y라 했을 때, if ((y1>y) != (y2>y)) 가 되고, 이를 어떤 경우에 참이 되는 지 진리표로 보면,
(y1>y) = T && (y2>y)=F 의 경우와, (y1>y)=F && (y2>y)=T의 경우만 참이 된다.
첫번 째 경우는, y가 (~,y1) 이고 (y2,~)일 때이고 (y1 밑 혹은 y2 위) 이는 가능하지 않은 경우이고
(y1보다 작으면서 y2보다 클 수 없음 혹은 그반대도 불가)
두번 째 경우는, y가 [y1,y2) 사이에 있을 때로, 가능한 경우이다. 즉, if ((y1>y) != (y2>y))은 y가 [y1,y2)사이에 있을 때라는 얘기.
- 점 q의 y좌표가, 다각형을 이루는 선분상의 y값 사이에 있다면,
이 때 q에서 이 선분으로 x축에 평행한 선을 그리면 만나는 점 atX를 구할 수 있다.
두 점 (x1,y1) (x2,y2)로 이루어진 선분에서, y값이 y0라면, 그 때의 x0값은?
y = ax +b 에서, a = (y2-y1)/(x2-x1), b=y1-ax1
x0 = 1/a(y0-b) --> 여기에 a, b값을 넣어 정리하면,
x0 = (x2-x1)(y0-y1)/(y2-y1) + x1
소스
bool isInside(P q, vector<P>& p) {
int cnt = 0;
int x, x1, x2, y, y1, y2;
x = q.x; y = q.y;
for (int i = 0; i < p.size(); ++i) {
int j = (i + 1) % p.size();
x1 = p[i].x; y1 = p[i].y;
x2 = p[j].x; y2 = p[j].y;
//핵심. [low..high) 임. 낮은쪽 점과 그 위쪽 라인을 지날 때만. 평행의 경우는 해당 안됨
if ((y1 > y) != (y2 > y)) {
//두 점을 이루는 직선상에서, y점에 대한 x값
double atX = (x2 - x1) * (y - y1) / (y2 - y1) + x1;
if (x < atX) ++cnt;
}
}
return (cnt % 2) > 0; //홀수이면 inside
}
6. convex hull
3)a[n]과 a[0]를 스택에 담고, a[1]~a[n]까지 진행하면서,
스택의 맨 위 두개 점으로 생기는 라인을 기준으로 새로 검사되는 점들의 CCW여부를 봐서,
- CCW가 아니면, 스택의 맨 위 점을 pop하면서, 다시 스택의 두 점을 기준으로한 라인과 그 점의 CCW 확인
- CCW이면 그 점을 스택에 넣음
for (int i = 2; i <= n; ++i) { //n-1이 아닌 n까지라는 것에 유의
while (ccw(st[st_top - 1], st[st_top],a[i]) <= 0) st_top--; //주의!!
st[++st_top] = a[i];
}
4)스택에 남아있는 점들의 집합이 convex hull을 구성하는 점 집합이 됨
소스
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define N 100003
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point() {}
Point(ll _x, ll _y) { x = _x; y = _y; }
Point operator - (const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); }
ll cross(Point q) { return (x*q.y - y*q.x); }
}mini, a[N], st[N];
int n;
ll ccw(Point p1, Point p2, Point p3) {
return (p2 - p1).cross(p3 - p1);
}
double dist(Point a, Point b) {
//여기서는, 상대적인 길이 대소만을 비교하는 것이기에 sqrt를 취하지 않음
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}
bool comp(Point a, Point b) {
ll cr = ccw(mini, a, b);
if (cr > 0 || (cr == 0 && dist(mini, a) < dist(mini, b))) return true;
return false;
}
int main() {
//freopen("convex_hull.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld %lld", &a[i].x, &a[i].y);
}
//graham
//1. find most below y. if same y, choose min x -> O(n)
mini = a[1];
for (int i = 2; i <= n; i++) {
if (mini.y > a[i].y || mini.y == a[i].y && mini.x > a[i].x) mini = a[i];
}
//2. sort
sort(a + 1, a + n + 1, comp);
//3. a[n]->a[0]에서부터 시작해서,
int st_top = 0;
st[0] = a[n]; //주의!!!
st[++st_top] = a[1];
for (int i = 2; i <= n; ++i) { //n-1이 아닌 n까지라는 것에 유의
while (ccw(st[st_top - 1], st[st_top], a[i]) <= 0) st_top--; //주의!!
st[++st_top] = a[i];
}
printf("%d", st_top);
return 0;
}
-끝-
'알고리즘 > 알고리즘 노트' 카테고리의 다른 글
| [다이나믹]타일채우기 문제들 (0) | 2016.07.26 |
|---|---|
| [다이나믹] (0) | 2016.07.26 |
| [그래프] (0) | 2016.07.24 |
| [이분탐색] (0) | 2016.07.23 |
| [완전탐색]DFS, BFS (0) | 2016.07.23 |