L2-054 三点共线

L2-054 三点共线 - java

L2-054 三点共线

语言	时间限制	内存限制	代码长度限制	栈限制
Java (javac)	2600 ms	512 MB	16KB	8192 KB
Python (python3)	2000 ms	256 MB	16KB	8192 KB
其他编译器	2000 ms	64 MB	16KB	8192 KB

题目描述：
给定平面上 $n$ 个点的坐标 $(x\_i, y\_i) (i = 1, \cdots, n)$ ，其中 $y$ 坐标只能是 $0$ 、 $1$ 或 $2$ ，是否存在三个不同的点位于一条非水平的直线上？

本题就请你找出所有共线的解。

输入格式：
输入首先在第一行给出正整数 $\le n \le 5 \times 10^4）$ ，为所有点的个数。
随后 $n$ 行，每行给出一个点的坐标：第一个数为 $x$ 轴坐标，第二个数为 $y$ 轴坐标。其中， $x$ 坐标是绝对值不超过 $10^6$ 的整数， $y$ 坐标在 ${ 0，1，2 \}$ 这三个数字中取值。同行数字间以空格分隔。

输出格式：
如果无解，则在一行中输出 -1。

如果有解，每一行输出共线的三个点坐标。每个点的坐标格式为 [x, y]，点之间用 1 个空格分隔，按照 y = $0$ 、 $1$ 、 $2$ 的顺序输出。

如果有多解，首先按照 y = 1 的 $x$ 坐标升序输出；还有相同则按照 y = 0 的 $x$ 坐标升序输出。

注意不能输出重复的解（即不能有两行输出是一样的内容）。题目保证任何一组测试的输出均不超过 $10^5$ 组不同的解。

输入样例：

输出样例：

[-10, 0] [-20, 1] [-30, 2]
[50, 0] [75, 1] [100, 2]
[90, 0] [75, 1] [60, 2]

输入样例：

输出样例：

-1

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

emmmmmmm

枚举每个前面两个点(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;}@Overridepublic 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 + x2int 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;}}