기하 ( ccw / 선분 교차 / 볼록 껍질 / rotating 캘리퍼스 / Line sweeping / Convex hull trick )

[WonYong-Jang]

ccw

public static int ccw(Point a, Point b, Point c)
{
	long op = ( (a.dx*b.dy)+(b.dx*c.dy)+(c.dx*a.dy) - (a.dy*b.dx) + (b.dy*c.dx)+(c.dy*a.dx) );
	if(op > 0) return 1; // 반시계 방향
	else if(op < 0) return -1; // 시계 방향
	else return 0; // 세점이 평행
}

다각형의 내부 외부 판별

다각형의 내부 외부 판별 구현

• 반직선은 항상 x축에 평행한 수평선임을 이용

반직선과 선분 사이에 교점이 존재하기 위한 조건은 2가지

1) 점 B의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.
2) 점 B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점 B의 좌표보다 크다.

=> 조건1을 만족하면 점 B를 지나는 수평 직선과 선분사이에 반드시 교점이 존재. 이때 오른쪽
반직선과의 교점만 세야 하므로 조건 2를 추가로 만족해야 반직선과 선분 사이의 교점 존재 여부를
올바르게 판별 가능!

public static boolean isCross(long tx, long ty)
{
	int crossCnt = 0;
	long mindy =0, maxdy =0;
	for(int i=0; i< N; i++)
	{
		Point p1 = p[i];
		Point p2 = p[(i+1) % N];
			
		mindy = min(p1.dy, p2.dy);
		maxdy = max(p1.dy, p2.dy);
			
		if(mindy <= ty && maxdy >= ty) // 선분 y 좌표 사이에 있는지 확인 
		{
				 
			long tmp = p2.dy - p1.dy; // 분모가 0 일 경우 제외 
			if(tmp == 0) continue;
			// 점과 직선사이의 수선의 발 좌표 공식
			long target = (ty - p1.dy)*(p2.dx - p1.dx) / (p2.dy - p1.dy) + p1.dx;
				
			if(tx < target) crossCnt++;
		}
	}
	if(crossCnt % 2 != 0) return true;
	else return false;
}

참고 링크 : https://bowbowbow.tistory.com/24

교차 판별

출처 : https://jason9319.tistory.com/358

[WonYong-Jang]

볼록 껍질

public class Main {

	static int N;
	static Point[] p = new Point[100005];
	static Point p0;
	static Stack<Integer> stack = new Stack<>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int dx =0, dy =0;
		p0 = new Point(40001,40001);
		for(int i=1; i<= N; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			p[i] = new Point(dx, dy);
			if(p0.dy > p[i].dy) {
				p0.dx = p[i].dx;
				p0.dy = p[i].dy;
			}
			if(p0.dy == p[i].dy && p0.dx > p[i].dx) {
				p0.dx = p[i].dx;
				p0.dy = p[i].dy;
			}
		}
		Arrays.sort(p, 1, N+1, new mySort()); // 각 정렬 ( 반시계 방향 기준 ) 
		
		stack.add(1);
		stack.add(2);
		int next = 3, second =0, first =0, op =0;
		while(next <= N)
		{
			while(stack.size() >= 2)
			{
				second = stack.pop();
				first = stack.peek();
				op = ccw(p[first], p[second], p[next]);
				if(op > 0) {
					stack.add(second);
					break;
				}
			}
			stack.push(next++);
		}
		System.out.println(stack.size());
	}
	public static int ccw(Point a, Point b, Point c)
	{
		long tmp = ((long)(a.dx*b.dy) + (long)(b.dx*c.dy) + (long)(c.dx*a.dy)) - ((long)(a.dy*b.dx) + (long)(b.dy*c.dx) + (long)(c.dy*a.dx));
		if(tmp > 0) return 1;
		else if(tmp < 0) return -1;
		else return 0;
	}
	public static long dis(Point a, Point b)
	{
		return (long)(a.dx-b.dx)*(a.dx-b.dx) + (long)(a.dy-b.dy)*(a.dy-b.dy);	
	}
	static class mySort implements Comparator<Point> {
		@Override
		public int compare(Point a, Point b) {
			int t = ccw(p0, a, b);
			if(t == 0)
			{
				long d1 = dis(p0,a);
				long d2 = dis(p0,b);
				if(d1 < d2) return -1;
				else if(d1 > d2) return 1;
				else return 0;
			}
			return t > 0 ? -1 : 1;
		}
	}
	static class Point {
		int dx, dy;
		Point(int a, int b) { 
			dx=a; dy=b;
		}
	}
}

[WonYong-Jang]

Convex Hull Trick

관련 문제 : 나무 자르기 (백준 13263 )

• 점화식 => dp[i] : i 번째 나무를 높이 1로 만드는데 필요한 최소 비용
• 나무를 자른 순간, 그 나무가 높이 1이었다면 높이를 1 깎아 완전히 벤 직후 해당 나무에 해당하는
  비용 B를 내면 됨.

[WonYong-Jang]

Line sweeping

2170 선 긋기

• x 좌표 기준 오름 차순 정렬
• 선분들을 차례로 순회하면서, 현재의 구간을 이어붙일 수 있는 한 최대한 이어 붙이다가
  더 이어붙일 수 없으면 이번 구간의 길이를 결과에 더하는 식으로 알고리즘 수행
• 왼쪽 끝 좌표가 같으면 어떤것 부터 순회하든 상관 없음

5419 북서풍

• 좌표가 같거나 커지고, y좌표가 같거나 작아지는 점 쌍이 몇개나 되는지를 구함
• y축에 평행한 수직선을 제일 왼쪽 끝에서부터 제일 오른쪽 끝으로 훑으면서 마주치는 점들마다
  이 점으로 항해할수 있는 점의 개수를 센다.
• 한 점 p를 잡았다면 x 좌표가 p의 것보다 작은 점들 중에서 y좌표는 p의 것보다 크거나 같은 점의
  개수를 세서 결과에 더함 !!
• x 좌표가 같은 점들이 존재한다면 y 좌표가 큰 것부터 방문하는게 좋음
• 점의 갯수 저장은 세그먼트 트리! ( 탱크 문제와 비슷 )
  참고 링크 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220907708368

2261 , 5620가장 가까운 두점 ( 분할정복, line sweeping 둘다 가능)

• x 값이 증가하는 순으로 정렬
• 두점 (arr[0], arr[1]) 사이의 거리를 최단거리로 초기 설정
• x축의 차이가 최단 거리보다 크다면 비교할 필요가 없기에 후보자를 걸러줌.
• y축을 기준으로 정렬된 후보자들을 통해 최단 거리를 갱신하게 된다.

링크 : http://m.blog.daum.net/rhaoslikesan/284?categoryId=30

7574 개구리

[WonYong-Jang]

Plane sweeping

관련 링크 : https://codedoc.tistory.com/421