AtCoder Beginner Contest 338 -- E - Chords -- 题解

目录

 E - Chords

题目描述：

思路解析：

代码实现 ：

 E - Chords

题目描述：

思路解析：

        弦上有没有交点，如果将结点1和结点2n之间的连接断开，其实可以等价于在1-2n的区间上，这n个线段是否有交点。 

这里我们使用栈来实现检查是否发生相交情况，遍历1-2n如果碰到一个线段的左端点将左端点加入栈中，如果碰到一个右端点，弹出栈中最后加入的左端点，如果左右端点不能匹配，则发生相交情况。

代码实现 ：

import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        int n = input.nextInt();
        int[] st = new int[2 * n];
        int[] cnt = new int[n];
        boolean loop = false;
        for (int i = 0; i < n; i++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
           st[a] = i;
           st[b] = i;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 2 * n; i++) {
            if (cnt[st[i]] == 0){
                cnt[st[i]]++;
                stack.add(st[i]);
            }else{
                if (stack.isEmpty() || st[i] != stack.pop()){
                    loop = true;
                    break;
                }
            }
        }
        if (loop) out.println("Yes");
        else out.println("No");
        out.flush();
        out.close();
        br.close();
    }


    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input input = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }

}