[기타/알고리즘] 서로 다른 색의 두 점의 쌍 구하기(컨벡스 헐)

 해당 문제는 학교 과제로 받은 문제이다. 문제의 요지는 빨간색점과 파란색점이 서로 교차하지않고 선을 그어야 한다.

처음에는 어떻게 해야할지 몰라 이리 저리 고민하다 컨벡스 헐 알고리즘이란 것을 발견하여 포스팅 하고자 여기에 쓴다. 이 문제는 최외곽의 점을 찾아 해당 점에서 반시계방향(시계방향으로 하여도 상관없음)회전하며 선을 차례대로 그었을때 해당 선에 의해서 나누어 지는 면에 속하는 파란색 점과 빨간색 점의 수를 동일하다면 그 때 선을 그어주고 분할정복기법을 이용해서 왼쪽 영역과 오른쪽 영역으로 나누어 각각 다시 분할정복을 수행해준다.

 

import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

import static java.lang.System.exit;

public class MyProblem1 {

    public static class Hull {
        int x, y;
        int color;

        public Hull(int x, int y, int color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }

    }

    public static Hull[] list;
    public static int n;
    public static StringBuilder sb = new StringBuilder();
    public static int cnt = 0;
    public static FileOutputStream output;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        File input = new File("D:\\study\\java_algo\\src\\com\\company\\input3.txt");
        output = new FileOutputStream("C:\\Users\\SAMSUNG\\Desktop\\Assignment #2 - (2) inputs\\output.txt");

        BufferedReader line = new BufferedReader(new FileReader(input));
        n = Integer.parseInt(line.readLine());

        list = new Hull[2 * n];

        sb.append(n + "\n");

        //Red || color 0
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(line.readLine(), " ");
            list[i] = new Hull(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt("0"));
        }

        //Blue || color 1
        for (int i = n; i < 2 * n; i++) {
            st = new StringTokenizer(line.readLine(), " ");
            list[i] = new Hull(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt("1"));
        }

        solve(0, list.length - 1);

        output.write(sb.toString().getBytes(StandardCharsets.UTF_8));

    }

    private static void solve(int start, int end) throws IOException {

        //만약 공간에 점이 두개만 있을때
        if (end - start == 1) {
            System.out.println(list[start].x + " " + list[start].y + ", " + list[end].x + " " + list[end].y);
            sb.append(list[start].x + " " + list[start].y + ", " + list[end].x + " " + list[end].y + "\n");

            return;
        }

        // 1. 기준점(가장 작은 수)찾음
        find_min(start, end);

        // 2. 반시계로 정렬
        Arrays.sort(list, start , end+1, new Comparator<Hull>() {

            @Override
            public int compare(Hull a, Hull b) {
                // TODO Auto-generated method stub
                int v = CCW(list[start], a, b);
                if (v > 0) return -1;
                if (v < 0) return 1;
               // return (Math.abs(a.x) + a.y) - (Math.abs(b.x) + b.y);
                return v;
            }
        });

        // 3. 처음으로 합이 1이 되는점 찾기
        int status = 0;
        for (int i = start + 1; i <= end; i++) {
            if (list[start].color == list[i].color) {
                status--;
            } else {
                status++;
            }

            if (status == 1) {
                System.out.println(list[start].x + " " + list[start].y + ", " + list[i].x + " " + list[i].y);
                sb.append(list[start].x + " " + list[start].y + ", " + list[i].x + " " + list[i].y + "\n");

                if(start+1 == i) {
                    solve(i + 1, end);
                }
                else if(end == i) {
                    solve(start + 1, end-1);
                }
                else if (start < i && i < end) {
                    solve(start + 1, i - 1);
                    solve(i + 1, end);
                }
                else{
                    System.out.println("error!");
                }

                break;
            }
        }
    }


    //==========================================================================================================

    // 벡터 외적구하는 메소드
    public static int CCW(Hull a, Hull b, Hull c) {
        long cal = (long) (b.x - a.x) * (c.y - a.y) - (long) (b.y - a.y) * (c.x - a.x);
        if (cal > 0)
            return 1;
        else if (cal < 0)
            return -1;
        else return 0;
    }

    // 볼록 껍질구한느 메소드(가장 작은 점 찾으면 무조건 볼록껍질에 속하기 떄문)
    public static void find_min(int start, int end) {
        for (int i = start; i < end; i++) {
            if (list[start].y > list[i].y || list[start].y == list[i].y && list[start].x > list[i].x) {
                Hull temp = list[start];
                list[start] = list[i];
                list[i] = temp;
            }
        }
    }
}