[자바] 백준 12781 - PIZZA ALVOLOC (java)

 문제 : boj12781

---

 

필요 알고리즘 개념

• 선분 교차 판정 (기하학, CCW)
  
  • 선분 교차 판정 알고리즘으로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  주어진 선분 2개로 피자가 4조각으로 나뉘는지 확인해보는건 결국 두 선분이 교차하는지 판단하면 된다.

CCW를 이용한 선분 교차 여부 판정을 보고 구현해주면 된다.

 

주의점은 위 설명에서는 교차된 것으로 판단되는 이하와 같은 케이스들은 이 문제에서는 교차하지 않는 것으로 판단해야 한다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Point implements Comparable<Point> {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o) {
        if (this.x == o.x)
            return this.y-o.y;
        return this.x-o.x;
    }
}

class Line {
    Point a, b;
    public Line(Point p1, Point p2) {
        a = p1.compareTo(p2)<=0?p1:p2;
        b = p1.compareTo(p2)<=0?p2:p1;
    }
    public Line(int x1, int y1, int x2, int y2) {
        this(new Point(x1, y1), new Point(x2, y2));
    }
    public boolean isIntersection(Line ano) {
        int res1 = Ccw.getCcw(this.a, this.b, ano.a) * Ccw.getCcw(this.a, this.b, ano.b);
        int res2 = Ccw.getCcw(ano.a, ano.b, this.a) * Ccw.getCcw(ano.a, ano.b, this.b);
        return res1<0 && res2<0;
    }
}

class Ccw {
    public static int getCcw(Point a, Point b, Point c) {
        Point[] arr = {a,b,c,a};
        long sum = 0;
        for (int i = 0; i < 3; i++) {
            sum += 1l*arr[i].x*arr[i+1].y-1l*arr[i+1].x*arr[i].y;
        }
        return sum>0?1:sum<0?-1:0;
    }
}

public class Main {
    private int ni(StringTokenizer st) { return Integer.parseInt(st.nextToken()); }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Line line1 = new Line(ni(st), ni(st), ni(st), ni(st));
        Line line2 = new Line(ni(st), ni(st), ni(st), ni(st));
        System.out.println(line1.isIntersection(line2)?1:0);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}