藍橋杯--平面切分--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);
    }
}