L2-054 三点共线 - java

题目解析

给定$n$个点，找到所有非水平共线组成的三个点的解

解题思路

枚举每个前面两个点(y=0 与 y=1 的点)是否存在 y=2的点使得三点共线。共线满足 (x2 - x1 = x3 - x2)

注： 由于题目当中给定的点存在相同位置，所以需要去重

代码

import java.io.*;
import java.util.*;

public class Main
{
    static int N = (int) 1e6, M = N * 2;
    static ArrayList<Integer> a = new ArrayList<>();
    static ArrayList<Integer> b = new ArrayList<>();
    static boolean[] A = new boolean[M + 10];
    static boolean[] B = new boolean[M + 10];
    static boolean[] C = new boolean[M + 10];

    static class edge implements Comparable<edge>
    {
        int x, y, z;

        public edge(int x1, int x2, int x3)
        {
            this.x = x1;
            this.y = x2;
            this.z = x3;
        }

        @Override
        public int compareTo(edge other)
        {
            if (this.y != other.y) return this.y - other.y;
            return this.x - other.x;
        }
    }

    public static void main(String[] args) throws IOException
    {
        int n = ini();
        for (int i = 1; i <= n; i++)
        {
            int x = ini(), y = ini();
            if (y == 0)
            {
                // 给定的多个点存在重复情况，所以需要去除重复的点
                if (!A[x + N]) a.add(x);
                A[x + N] = true;
            }
            else if (y == 1)
            {
                if (!B[x + N]) b.add(x);
                B[x + N] = true;
            }
            else if (y == 2) C[x + N] = true;
        }

        // 将给定的点进行排序
        Collections.sort(a);
        Collections.sort(b);

        ArrayList<edge> edges = new ArrayList<>();
        for (int x1 : a)
        {
            for (int x2 : b)
            {
                // 给定的点满足共线， x2 - x1 = x3 - x2 => x3 = x2 - x1 + x2
                int x3 = x2 - x1 + x2;
                // 当x3的绝对值在N的范围内，并且该点存在
                if (Math.abs(x3) <= N && C[x3 + N]) edges.add(new edge(x1, x2, x3));
            }
        }

        if (!edges.isEmpty())
        {
            // 按照题目要求，先按照y=1的x升序，再按照y=0的x升序排序
            Collections.sort(edges);

            for (int i = 0; i < edges.size(); i++)
            {
                if (i != 0) out.println();
                out.printf("[%d, 0] [%d, 1] [%d, 2]", edges.get(i).x, edges.get(i).y, edges.get(i).z);
            }
        }
        else out.println(-1);

        out.flush();
        out.close();
    }

    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(System.out);

    static int ini() throws IOException
    {
        sc.nextToken();
        return (int) sc.nval;
    }

}

ArrayList
ArrayList

Collections.sort

团体程序设计天梯赛-练习集-java