글 읽기 - 10875번 뱀 문제, 반례 찾는거 도움 부탁드립니다

stack 7년 전 3

반례나 소스에서 잘못된 점 있는지 도움 부탁드립니다.

알고리즘은

O(n^2)으로 풀려고 했고, 선분들을 저장한 다음에 교차 여부를 판단했습니다.

<시도한 테스트 케이스>

TestCase #1

3
4
2 L
2 L
1 L
5 R

=> 7

TestCase #2
3
3
2 L
4 L
4 R

=> 6

TestCase #3
3
3
2 R
1 R
10 R

= 9

TestCase #4
3
3
2 R
10 L
4 R

= 6

TestCase #5
3
3
2 L
10 L
4 R

= 6

TestCase #6
3
3
10 L
4 L
4 R

= 4

TestCase #7
3
3
2 L
4 L
4 R

= 6

TestCase #8
3
4
2 L
2 L
1 L
5 R

= 7

TestCase #9
3
4
2 R
2 R
1 R
5 L

= 7

TestCase #10
3
5
2 R
3 L
1 L
2 L
10 L

= 9

TestCase #11
3
5
2 R
3 R
1 R
2 R
10 L

= 9

TestCase #12
3
5
2 R
3 R
1 R
2 L
10 L

= 13

TestCase #13
3
8
3 R
3 R
6 R
6 R
6 R
2 R
10 L
10 R

= 32

TestCase #14
3
4
3 R
3 R
3 R
3 R

= 12

TestCase #15
3
4
3 R
3 R
3 R
2 R

TestCase #16
100000000
4
2 L
2 L
1 L
5 R

TestCase #17
1
6
1 L
1 L
2 L
2 L
2 L
2 L

TestCase #18
3
8
2 L
2 L
3 L
4 L
4 L
5 L
2 L
7 L

TestCase #19
3
8
2 L
2 L
3 L
4 L
4 L
10 L
2 L
7 L

TestCase #20
8
11
1 L
4 R
1 R
8 L
1 L
8 R
1 R
8 L
1 L
6 L
10 R

TestCase #21
3
1
1 L

TestCase #22
3
1
1 R
5

TestCase #23
3
2
1 R
1 R

TestCase #24
3
2
1 R
1 L
5

TestCase #25
3
1
10 L
4

TestCase #26
3
3
2 L
4 L
4 R

TestCase #27
3
3
1 R
1 R
10 L

TestCase #28
3
3
1 R
1 L
10 L

TestCase #29
3
0

TestCase #30
3
14
3 L
1 L
3 R
1 R
3 L
1 L
6 L
1 L
5 R
1 R
4 L
3 L
1 L
2 L

TestCase #31
3
16
3 L
1 L
3 R
1 R
3 L
1 L
6 L
6 L
1 L
5 R
1 R
5 L
4 L
1 L
3 R
1 R

TestCase #32
3
16
3 L
1 L
3 R
1 R
3 L
1 L
6 L
6 L
1 L
5 R
1 R
5 L
4 L
1 L
3 R
2 R

TestCase #33
3
17
3 L
1 L
3 R
1 R
3 L
1 L
6 L
6 L
1 L
5 R
1 R
5 L
4 L
1 L
3 R
1 R
3 L

TestCase #34
3
1
1 L

TestCase #35
1
1
1 L

TestCase #36
3
5
3 L
1 L
6 L
1 L
2 L

TestCase #37
3
5
3 L
1 L
6 L
1 L
2 R

TestCase #37
3
5
3 L
1 L
6 L
1 L
3 R

TestCase #37
3
5
3 L
1 L
6 L
1 L
100000 R

4
4
1 L
1 L
2 L
1 L

4
5
1 L
1 R
1 R
1 R
10 L

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

/**
 * BOJ#10875 뱀
 * https://www.acmicpc.net/problem/10875
 */

public class Main2 {

    static final int LEFT = 0;
    static final int UP = 1;
    static final int RIGHT = 2;
    static final int DOWN = 3;

    static final long MOD = 10000000;

    public static void main(String[] args) throws IOException {

        boolean isAdded = false;
        int L; // map 의 크기 <= 100,000,000
        int N; // 머리 회전 횟수 <= 1,000
        LineInfo[] info;

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        L = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());

        info = new LineInfo[N + 1];

        Point curPoint = new Point(L, L);
        int curDir = RIGHT;

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int time = Integer.parseInt(st.nextToken());
            char rotate = st.nextToken().charAt(0);

            int nextDir = changeDir(rotate, curDir);
            switch (curDir) {

                case LEFT:
                    info[i] = new LineInfo(new Point(curPoint.x - time, curPoint.y),
                            new Point(curPoint.x, curPoint.y), time, LEFT, nextDir);

                    curPoint.x = info[i].start.x;
                    curPoint.y = info[i].start.y;
                    break;

                case UP:
                    info[i] = new LineInfo(new Point(curPoint.x, curPoint.y - time),
                            new Point(curPoint.x, curPoint.y), time, UP, nextDir);

                    curPoint.x = info[i].start.x;
                    curPoint.y = info[i].start.y;
                    break;

                case RIGHT:
                    info[i] = new LineInfo(new Point(curPoint.x, curPoint.y),
                            new Point(curPoint.x + time, curPoint.y), time, RIGHT, nextDir);

                    curPoint.x = info[i].end.x;
                    curPoint.y = info[i].end.y;
                    break;

                case DOWN:
                    info[i] = new LineInfo(new Point(curPoint.x, curPoint.y),
                            new Point(curPoint.x, curPoint.y + time), time, DOWN, nextDir);

                    curPoint.x = info[i].end.x;
                    curPoint.y = info[i].end.y;
                    break;
            }

            curDir = nextDir;
        }

        if (curPoint.x >= 0 && curPoint.x <= 2 * L && curPoint.y >= 0 && curPoint.y <= 2 * L) {

            isAdded = true;

            switch (curDir) {

                case LEFT:
                    info[N] = new LineInfo(new Point(curPoint.x - (2 * L + 1), curPoint.y),
                            new Point(curPoint.x, curPoint.y), (2 * L + 1), curDir, curDir);
                    break;

                case UP:
                    info[N] = new LineInfo(new Point(curPoint.x, curPoint.y - (2 * L + 1)),
                            new Point(curPoint.x, curPoint.y), (2 * L + 1), curDir, curDir);
                    break;

                case RIGHT:
                    info[N] = new LineInfo(new Point(curPoint.x, curPoint.y),
                            new Point(curPoint.x + (2 * L + 1), curPoint.y), (2 * L + 1), curDir, curDir);
                    break;

                case DOWN:
                    info[N] = new LineInfo(new Point(curPoint.x, curPoint.y),
                            new Point(curPoint.x, curPoint.y + (2 * L + 1)), (2 * L + 1), curDir, curDir);
                    break;
            }
        }

        // solve

        // O(N^2)
        long bodyCollisionTime = Long.MAX_VALUE;
        long boundaryCollisionTime = 0;
        long notCollisionTime = 0;
        boolean isBoundaryCollision = false;
        boolean isBodyCollision = false;

        //for (int i = 0; i < (isAdded ? N + 1 : N) && !isBoundaryCollision; i++) {
        for (int i = 0; i < (isAdded ? N + 1 : N); i++) {

            long collisionTime = 0;
            for (int j = i + 2; j < (isAdded ? N + 1 : N); j++) {
                //for (int j = N-1; j > i+1; j--) {

                if (i == j) {

                    continue;
                }

                // 1. check body collision
                if (checkBodyCollision(info[i], info[j])) {

                    for (int k = 0; k < j; k++) {

                        collisionTime += info[k].time;
                    }
                    collisionTime += calcBodyCollision(info[j], info[i]);

                    isBodyCollision = true;
                    bodyCollisionTime = bodyCollisionTime > collisionTime ? collisionTime : bodyCollisionTime;

                    break;
                }

            } // inner loop


            // 2. check boundary collision
            long diff = checkBoundaryCollision(info[i], L);
            if (diff > 0) {

                for (int k = 0; k < i; k++) {

                    boundaryCollisionTime += info[k].time;
                }
                boundaryCollisionTime += diff;

                isBoundaryCollision = true;
                break;
            }

        }// outer loop

        if (isBoundaryCollision) {

            System.out.println(Math.min(bodyCollisionTime, boundaryCollisionTime));
        } else if (!isBodyCollision && !isBoundaryCollision) {

            for (int i = 0; i < N; i++) {

                notCollisionTime += info[i].time;
            }

            if (N == 0) {

                notCollisionTime = L + 1;
            } else {

                notCollisionTime += calcNotCollisionTime(info[N - 1], L);
            }

            System.out.println(notCollisionTime);
        } else {

            System.out.println(bodyCollisionTime);
        }
    }

    static long calcNotCollisionTime(LineInfo line, int L) {

        long diff = 0;

        switch (line.nextDir) {

            case LEFT:

                diff = line.start.x - 0;
                break;

            case UP:

                diff = line.start.y - 0;
                break;

            case RIGHT:

                diff = (2 * L) - line.end.x;
                break;

            case DOWN:

                diff = (2 * L) - line.end.y;
                break;
        }

        return diff > 0 ? diff + 1 : 0;
    }

    static long calcBodyCollision(LineInfo line1, LineInfo line2) {

        long diff = 0;

        switch (line1.dir) {

            case LEFT:

                diff = line1.end.x - line2.end.x;
                break;

            case UP:
                diff = line1.end.y - line2.end.y;
                break;

            case RIGHT:
                diff = line2.start.x - line1.start.x;
                break;

            case DOWN:
                diff = line2.start.y - line1.start.y;
                break;
        }

        return diff;
    }

    static boolean checkBodyCollision(LineInfo line1, LineInfo line2) {

        //boolean ret1 = false, ret2 = false;
        long p1, p2 = 0;

        //-> fn(A, B, C) = (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3)
        //-> fn(A, B, D) = (x1y2 - x2y1) + (x2y4 - x4y2) + (x4y1 - x1y4)

        // 1. line1, line2
        p1 = (line1.start.x * line1.end.y - line1.end.x * line1.start.y) + (line1.end.x * line2.start.y - line2.start.x * line1.end.y) + (line2.start.x * line1.start.y - line1.start.x * line2.start.y);
        p2 = (line1.start.x * line1.end.y - line1.end.x * line1.start.y) + (line1.end.x * line2.end.y - line2.end.x * line1.end.y) + (line2.end.x * line1.start.y - line1.start.x * line2.end.y);

        p1 %= MOD;
        p2 %= MOD;

        long product1 = (p1 * p2) % MOD;

        // 2. line2, line1
        p1 = (line2.start.x * line2.end.y - line2.end.x * line2.start.y) + (line2.end.x * line1.start.y - line1.start.x * line2.end.y) + (line1.start.x * line2.start.y - line2.start.x * line1.start.y);
        p2 = (line2.start.x * line2.end.y - line2.end.x * line2.start.y) + (line2.end.x * line1.end.y - line1.end.x * line2.end.y) + (line1.end.x * line2.start.y - line2.start.x * line1.end.y);

        p1 %= MOD;
        p2 %= MOD;

        long product2 = (p1 * p2) % MOD;

        // 둘다 < 0 : 교차
        if (product1 < 0 && product2 < 0) {

            return true;
        }
        // 같은 부호 : 교차X
        else if (product1 * product2 > 0) {

            return false;
        }

        // 하나는 음수 하나는 양수 : 교차 X
        else if (product1 * product2 < 0) {

            return false;
        }

        // 둘중 하나만 0
        else if (product1 + product2 != 0 && product1 * product2 == 0) {

            return false;
        }

        // 둘다 0 : 충돌하거나 충돌하지 않음
        else if (product1 == 0 && product2 == 0) {

            // 수직
            if ((line1.dir + line2.dir) % 2 != 0) {

                if (product1 == 0 && product2 == 0) {

                    return true;
                } else {

                    return false;
                }
            }
            // 수평
            else {

                // 세로
                if (line1.dir == UP || line1.dir == DOWN) {

                    if ((line1.start.y < line2.start.y && line1.end.y < line2.start.y) ||
                            (line2.start.y < line1.start.y && line2.end.y < line1.start.y)) {

                        return false;
                    }

                    return true;
                }

                // 가로
                else {

                    if ((line1.start.x < line2.start.x && line1.end.x < line2.start.x) ||
                            (line2.start.x < line1.start.x && line2.end.x < line1.start.x)) {

                        return false;
                    }

                    return true;
                }
            }
        }

        return false;
    }


    static long checkBoundaryCollision(LineInfo line, int L) {

        long diff = 0;

        switch (line.dir) {

            case LEFT:
                if (line.start.x < 0) {

                    diff = line.end.x - 0;
                }
                break;

            case UP:
                if (line.start.y < 0) {

                    diff = line.end.y - 0;
                }
                break;

            case RIGHT:
                if (line.end.x > 2 * L) {

                    diff = (2 * L) - line.start.x;
                }
                break;

            case DOWN:
                if (line.end.y > 2 * L) {

                    diff = (2 * L) - line.start.y;
                }
                break;
        }

        return diff > 0 ? diff + 1 : 0;
    }


    static int changeDir(char rotate, int curDir) {

        // direction
        if (rotate == 'L') {

            curDir = curDir - 1 < 0 ? 3 : curDir - 1;
        } else if (rotate == 'R') {

            curDir = curDir + 1 > 3 ? 0 : curDir + 1;
        }

        return curDir;
    }
}

class LineInfo {

    Point start;
    Point end;
    int time;
    int dir;
    int nextDir;

    LineInfo(Point start, Point end, int time, int dir, int nextDir) {

        this.start = start;
        this.end = end;
        this.time = time;
        this.dir = dir;
        this.nextDir = nextDir;
    }

    @Override
    public String toString() {

        return "(" + start.x + "," + start.y + ") <-> (" + end.x + "," + end.y + ")"
                + ", dir=" + (dir == 0 ? "LEFT" : dir == 1 ? "UP" : dir == 2 ? "RIGHT" : "DOWN");
    }
}

class Point {

    int x;
    int y;

    Point(int x, int y) {

        this.x = x;
        this.y = y;
    }
}