蓝桥杯--平面切分--java

题目描述

平面上有 N 条直线，其中第 i 条直线是 y = A i × x + B i y=A_i ×x+B_i y=Ai​×x+Bi​

请计算这些直线将平面分成了几个部分。

输入描述

第一行包含一个整数 N以下 N 行，每行包含两个整数 A i​ ,B i​ 。

其中， 1 ≤ N ≤ 1000 , − 1 0 5 ≤ A i ​ , B i ​ ≤ 1 0 5 1≤N≤1000,−10^5 ≤A _i​ ,B_i​ ≤10^5 1≤N≤1000,−105≤Ai​​,Bi​​≤105 。

输出描述

一个整数代表答案。

输入输出样例

输入

3
1 1
2 2
3 3
           

输出

6
           

运行限制

最大运行时间：1s

最大运行内存: 256M

习题解答

找规律我倒是花了挺多时间的

思路分析

对于一个面而言 ，任意一条直线可将其分为2个面（即多加了一个面）

此时来进行加线的分析：

对于加的线，就会多一个面。

遍历已经有线：

1.如果平行：则没有附加的，和上面平常一样的（共加1）。

2.如果和一个相交，会附加多一个（共加2）。

相当于分割了这条线后面的面
           

3.如果相交点重复，则不会附加（共加1）。

此时分割的面重复，不加了。
           

代码实现

需要删除重复的线：即a和b相同

遍历已经有的线后，用set来去重。（上面这个去重也可以用set，可以把a和b当作点的x和y去重）

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 在此输入您的代码...
        int n = sc.nextInt();
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
            for(int j=0;j<i;j++){
                if(a[i][0]==a[j][0]&&a[i][1]==a[j][1]){
                    i--;
                    n--;
                    break;
                }
            }
        }
        int count = 2;
        for (int i = 1; i < n; i++) {
            int c = 1;
            Set<Point> set = new HashSet<>();
            for (int j = 0; j < i; j++) {
                if (a[i][0] == a[j][0]){
                    continue;
                }
                double x = (a[i][1] - a[j][1])*1.0 / (a[j][0] - a[i][0]) + 0.0;
                double y = a[i][0] * x + a[i][1] + 0.0;
                Point p = new Point(x, y);//相交点
                if (!set.contains(p)) {
                    set.add(p);
                    c++;
                }
            }
            count+=c;
        }
        
        System.out.println(count);
        sc.close();
    }

    
}
class Point {
    private double x;
    private double y;

    public Point(Double x, Double y) {
        this.x = x;
        this.y = y;
    }
    //重写equals和hashCode方法
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x &&
                y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}