글 읽기 - 반례를 못찾겠어요!

paperfrog 5년 전 0

CCW 알고리즘 이용해서 선분 교차 판별 한 뒤

각 꼭지점을 지나 갈 경우 중복되었으니

그 때 마다 --하여 중복 개수를 제거하였는데

반례를 못찾겠어요..

import java.util.*;
import java.lang.*;

class Main {
    static int count;
    static Scanner scan = new Scanner(System.in);
    static int xmin;
    static int ymin;
    static int xmax;
    static int ymax;
    static int x1;
    static int y1;
    static int x2;
    static int y2;

    static void solve() {
        count = 0;
        xmin = scan.nextInt();
        ymin = scan.nextInt();
        xmax = scan.nextInt();
        ymax = scan.nextInt();
        x1 = scan.nextInt();
        y1 = scan.nextInt();
        x2 = scan.nextInt();
        y2 = scan.nextInt();


        count += isCrossed(x1, y1, x2, y2, xmin, ymin, xmin, ymax);
        count += isCrossed(x1, y1, x2, y2, xmin, ymin, xmax, ymin);
        count += isCrossed(x1, y1, x2, y2, xmax, ymin, xmax, ymax);
        count += isCrossed(x1, y1, x2, y2, xmin, ymax, xmax, ymax);

        if (count == 2 || count == 4) {
            if (isCrossed(x1, y1, x2, y2, xmin, ymax, xmin, ymax) >= 1)
                count--;
            if (isCrossed(x1, y1, x2, y2, xmin, ymin, xmin, ymin) >= 1)
                count--;
            if (isCrossed(x1, y1, x2, y2, xmax, ymin, xmax, ymin) >= 1)
                count--;
            if (isCrossed(x1, y1, x2, y2, xmax, ymax, xmax, ymax) >= 1)
                count--;
        }
        System.out.println(count >= 4 ? 4 : count);
    }

    static int isCrossed(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { //직선 ab랑 cd의 교차 여부 알 때
        int chk1 = ccw(x1, y1, x2, y2, x3, y3);
        int chk2 = ccw(x1, y1, x2, y2, x4, y4);
        int chk3 = ccw(x3, y3, x4, y4, x1, y1);
        int chk4 = ccw(x3, y3, x4, y4, x2, y2);

        if (chk1 == 0 && chk2 == 0 && chk3 == 0 && chk4 == 0) {
            if (isOverlapped(x1, y1, x2, y2, x3, y3, x4, y4) == true) {
                return 50;
            }
            return 0;
        }
        if (chk1 * chk2 <= 0 && chk3 * chk4 <= 0) {
            return 1;
        }
        return 0;
    }

    static boolean isOverlapped(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
        if (Math.max(x1, x2) < Math.min(x3, x4)) {
            return false;
        }
        if (Math.min(x1, x2) > Math.max(x3, x4)) {
            return false;
        }
        if (Math.max(y1, y2) < Math.min(y3, y4)) {
            return false;
        }
        if (Math.min(y1, y2) > Math.max(y3, y4)) {
            return false;
        }
        return true;
    }

    static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
        int a = x1 * y2 + x2 * y3 + x3 * y1;
        int b = y1 * x2 + y2 * x3 + y3 * x1;
        if ((a - b) > 0) return 1;
        else if (a - b == 0) return 0;
        else return -1;
    }

    public static void main(String[] args) {
        int t = scan.nextInt();
        while (t > 0) {
            solve();
            t--;
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠어요!

paperfrog 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말