个人ACM模板总结（JAVA版）（四）

个人ACM模板总结（JAVA版）（四）

感谢AcWing – 快乐学习生活，尽在AcWing Acwing这个算法平台。

学习自Acwing + 大佬（青衫白衣98）+ 自己总结

七、其他

（一）排序

1.快速排序

public class QuickSort {
            
    public static void quickSort(int[] arr, int l, int r) {
            
        if (l >= r) return;
        int x = arr[(l + r) / 2];
        int i = l - 1, j = r + 1;
        while (i < j) {
            
            do i++; while (arr[i] < x);
            do j--; while (arr[j] > x);
            if (i < j) {
            
                swap(arr, i, j);
            }
        }
        quickSort(arr, l, j);
        quickSort(arr, j + 1, r);
    }

    private static void swap(int[] arr, int i, int j) {
            
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
            
        int[] a = {
            5, 3, 8, 4, 2};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

2.归并排序

public class MergeSort {
            
    private static int[] tmp;

    public static void mergeSort(int[] arr, int l, int r) {
            
        if (l >= r) return;
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        tmp = new int[r - l + 1];
        int i = l, j = m + 1, k = 0;

        while (i <= m && j <= r) {
            
            if (arr[i] <= arr[j]) {
            
                tmp[k++] = arr[i++];
            } else {
            
                tmp[k++] = arr[j++];
            }
        }

        while (i <= m) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];

        for (int p = 0; p < tmp.length; p++) {
            
            arr[l + p] = tmp[p];
        }
    }

    public static void main(String[] args) {
            
        int[] a = {
            5, 3, 8, 4, 2};
        mergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

3.归并排序求逆序对

public class InversionCount {
            
    private static int[] tmp;

    public static long mergeSort(int[] arr, int l, int r) {
            
        if (l >= r) return 0;
        int mid = (l + r) / 2;
        long res = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r);

        tmp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r) {
            
            if (arr[i] <= arr[j]) {
            
                tmp[k++] = arr[i++];
            } else {
            
                tmp[k++] = arr[j++];
                res += mid - i + 1;
            }
        }

        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];

        for (int p = 0; p < tmp.length; p++) {
            
            arr[p + l] = tmp[p];
        }

        return res;
    }

    public static void main(String[] args) {
            
        int[] a = {
            3, 1, 2, 4, 5};
        System.out.println("逆序对数量：" + mergeSort(a, 0, a.length - 1));
    }
}

（二）二分

1.整数二分

public class BinarySearch {
            

    // 区间 [l, r] 被划分为 [l, mid] 和 [mid+1, r]
    public static int binarySearch1(int[] arr, int target) {
            
        int l = 0, r = arr.length - 1;
        while (l < r) {
            
            int mid = (l + r) / 2;
            if (arr[mid] >= target) {
            
                r = mid;
            } else {
            
                l = mid + 1;
            }
        }
        return l;
    }

    // 区间 [l, r] 被划分为 [l, mid-1] 和 [mid, r]
    public static int binarySearch2(int[] arr, int target) {
            
        int l = 0, r = arr.length - 1;
        while (l < r) {
            
            int mid = (l + r + 1) / 2;
            if (arr[mid] <= target) {
            
                l = mid;
            } else {
            
                r = mid - 1;
            }
        }
        return l;
    }
}

2.浮点数二分

public class FloatBinarySearch {
            
    public static double binarySearch(double l, double r) {
            
        for (int i = 0; i < 100; i++) {
            
            double mid = (l + r) / 2;
            if (check(mid)) {
            
                r = mid;
            } else {
            
                l = mid;
            }
        }
        return l;
    }

    // 示例 check 函数：找 sqrt(2)
    public static boolean check(double x) {
            
        return x * x >= 2.0;
    }

    public static void main(String[] args) {
            
        System.out.println(binarySearch(1, 2)); // 输出近似值 1.414...
    }
}

（三）快速幂和龟速乘

1. 龟速乘法（防止溢出的大数相乘）

public class SlowMultiply {
            
    public static long multiply(long a, long b, long mod) {
            
        long res = 0;
        while (b > 0) {
            
            if ((b & 1) == 1) {
            
                res = (res + a) % mod;
            }
            a = (a + a) % mod;
            b >>= 1;
        }
        return res;
    }
}

2. 快速幂（模幂运算）

public class FastPower {
            
    public static long power(long base, long exp, long mod) {
            
        long ans = 1;
        while (exp != 0) {
            
            if ((exp & 1) == 1) {
            
                ans = ans * base % mod;
            }
            base = base * base % mod;
            exp >>= 1;
        }
        return ans;
    }
}

---

（四）快读

import java.io.*;

public class FastReader {
            
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    public static void init() {
            
        reader = new BufferedReader(new InputStreamReader(System.in));
    }

    public static String next() throws IOException {
            
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            
            String line = reader.readLine();
            if (line == null) throw new IOException("No more input");
            tokenizer = new StringTokenizer(line);
        }
        return tokenizer.nextToken();
    }

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

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

    public static double nextDouble() throws IOException {
            
        return Double.parseDouble(next());
    }

    public static void main(String[] args) throws IOException {
            
        init();
        int n = nextInt();
        System.out.println(n);
    }
}

（五）高精度

_int128 a;//可以防止爆longlong，注意两个

1.大数相加：

import java.util.*;

public class HighPrecisionAddition {
            
    public static List<Integer> add(List<Integer> A, List<Integer> B) {
            
        List<Integer> C = new ArrayList<>();
        int t = 0; // 进位
        for (int i = 0; i < A.size() || i < B.size(); i++) {
            
            if (i < A.size()) t += A.get(i);
            if (i < B.size()) t += B.get(i);
            C.add(t % 10);
            t /= 10;
        }
        if (t > 0) C.add(t);
        return C;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();

        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();

        for (int i = s1.length() - 1; i >= 0; i--) A.add(s1.charAt(i) - '0');
        for (int i = s2.length() - 1; i >= 0; i--) B.add(s2.charAt(i) - '0');

        List<Integer> C = add(A, B);

        for (int i = C.size() - 1; i >= 0; i--) {
            
            System.out.print(C.get(i));
        }
    }
}

2.高精度减：

import java.util.*;

public class HighPrecisionSubtraction {
            
    public static boolean cmp(List<Integer> A, List<Integer> B) {
            
        if (A.size() != B.size()) return A.size() > B.size();
        for (int i = A.size() - 1; i >= 0; i--)
            if (!A.get(i).equals(B.get(i))) return A.get(i) > B.get(i);
        return true;
    }

    public static List<Integer> sub(List<Integer> A, List<Integer> B) {
            
        List<Integer> C = new ArrayList<>();
        int t = 0;
        for (int i = 0; i < A.size(); i++) {
            
            t = A.get(i) - t;
            if (i < B.size()) t -= B.get(i);
            C.add((t + 10) % 10);
            t = t < 0 ? 1 : 0;
        }

        while (C.size() > 1 && C.get(C.size() - 1) == 0)
            C.remove(C.size() - 1);
        return C;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();

        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();

        for (int i = s1.length() - 1; i >= 0; i--) A.add(s1.charAt(i) - '0');
        for (int i = s2.length() - 1; i >= 0; i--) B.add(s2.charAt(i) - '0');

        if (cmp(A, B)) {
            
            List<Integer> C = sub(A, B);
            for (int i = C.size() - 1; i >= 0; i--) System.out.print(C.get(i));
        } else {
            
            List<Integer> C = sub(B, A);
            System.out.print("-");
            for (int i = C.size() - 1; i >= 0; i--) System.out.print(C.get(i));
        }
    }
}

3.高精度除低精度：（返回商和余数）

import java.util.*;

public class HighPrecisionDivision {
            
    public static class Result {
            
        List<Integer> quotient;
        int remainder;

        public Result(List<Integer> q, int r) {
            
            quotient = q;
            remainder = r;
        }
    }

    public static Result divide(List<Integer> A, int b) {
            
        List<Integer> C = new ArrayList<>();
        int r = 0;
        for (int i = A.size() - 1; i >= 0; i--) {
            
            r = r * 10 + A.get(i);
            C.add(r / b);
            r %= b;
        }
        Collections.reverse(C);
        while (C.size() > 1 && C.get(0) == 0) C.remove(0);
        return new Result(C, r);
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        int b = sc.nextInt();

        List<Integer> A = new ArrayList<>();
        for (int i = s1.length() - 1; i >= 0; i--) A.add(s1.charAt(i) - '0');

        Result res = divide(A, b);
        for (int digit : res.quotient) System.out.print(digit);
        System.out.println("
余数：" + res.remainder);
    }
}

4.高精度乘低精度

import java.util.*;

public class HighPrecisionMultiplicationLow {
            
    public static List<Integer> multiply(List<Integer> A, int b) {
            
        List<Integer> C = new ArrayList<>();
        int t = 0;
        for (int digit : A) {
            
            t += digit * b;
            C.add(t % 10);
            t /= 10;
        }
        while (t > 0) {
            
            C.add(t % 10);
            t /= 10;
        }
        while (C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
        return C;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        int b = sc.nextInt();

        List<Integer> A = new ArrayList<>();
        for (int i = s1.length() - 1; i >= 0; i--) A.add(s1.charAt(i) - '0');

        List<Integer> C = multiply(A, b);
        for (int i = C.size() - 1; i >= 0; i--) System.out.print(C.get(i));
    }
}

5.高精度乘高精度

import java.util.*;

public class HighPrecisionMultiplicationHigh {
            
    public static String multiply(String s1, String s2) {
            
        int len1 = s1.length();
        int len2 = s2.length();
        int[] result = new int[len1 + len2];

        for (int i = 0; i < len1; i++) {
            
            for (int j = 0; j < len2; j++) {
            
                result[i + j] += (s1.charAt(i) - '0') * (s2.charAt(j) - '0');
            }
        }

        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = 0; i < len1 + len2; i++) {
            
            int sum = carry + result[i];
            sb.append(sum % 10);
            carry = sum / 10;
        }

        while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0')
            sb.deleteCharAt(sb.length() - 1);

        return sb.reverse().toString();
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        System.out.println(multiply(a, b));
    }
}

补充：

如需更高效的高精度运算，可使用 BigInteger 类，例如：

import java.math.BigInteger;

public class BigIntegerExample {
            
    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();
        System.out.println("加法: " + a.add(b));
        System.out.println("减法: " + a.subtract(b));
        System.out.println("乘法: " + a.multiply(b));
        System.out.println("除法: " + a.divide(b));
    }
}

不过在竞赛中，手动实现更可控，也更有助于理解底层逻辑。

八、Java高精度

（一）java参考代码：

参考一：

//import java.util.Scanner;//相当于输入输出头文件
import java.util.*;//啥都有头文件
//import java.math.BigInteger;//大数类
import java.math.BigDecimal;//大浮点数
import java.math.*;//关于数学的头文件
public class Main {
            
   public static void main(String[] args) {
            
       BigInteger[] sum=new BigInteger[105];//开一个数组
       Scanner cin = new Scanner(System.in);//必须要写这句话（输入）
       int t = cin.nextInt();//输入整数T nextInt() 下一个int型数据
//        while(cin.hasNext()) {//循环输入，hasNext()
//             int n = cin.nextInt();
//        }
       while (t--!=0) {
            //java里不能直接写while(t--)，必须是只有真假的表达式
           BigInteger a = cin.nextBigInteger();//输入下一个大数
           BigInteger b = cin.nextBigInteger();//输入下一个大数
           BigInteger c;
           c = a.add(b);//c=a+b
           c = a.subtract(b);//c=a-b
           c = a.multiply(b);//c=a*b
           c = a.divide(b);//c=a/b(整数除法)
           c = a.remainder(b);//c=a%b
           c = a.mod(b);//c=a%b(结果为正数)
           c = BigInteger.ZERO;//c=0
           c = BigInteger.ONE;//c=1
           c = BigInteger.TEN;//c=10 java大数中只有0,1,10
           c = BigInteger.valueOf(7);//c=7
           int n = 7;
           c = BigInteger.valueOf(n);//c=n
           c = a.pow(n);//幂运算 c=pow(a,n)
           c = a.gcd(b);//最大公约数 c=gcd(a,b)
           c = a.abs();//
           c = a.max(b);//c=max(a,b)
           c = a.min(b);//c=min(a,b)
           n = a.compareTo(b);//a<b n=-1;a=b n=0;a>b n=1
           a.equals(b);//a==b
           a.isProbablePrime(2);//判断素数，有一定几率错误，最好手写
           System.out.println(c);//输出c并换行
           System.out.print(c);//输出c
           System.out.println(a+" "+b);//输出a空格b
           BigDecimal d = cin.nextBigDecimal();//输入下一个高精度浮点数
           BigDecimal e = cin.nextBigDecimal();//输入下一个高精度浮点数
           BigDecimal f = d.add(e);//f=d+e
           //...其他和大数类似
           f = d.setScale(2);//保留2位小数，默认四舍五入
           f = d.setScale(2,BigDecimal.ROUND_DOWN);//保留2位小数，向下取整
           f = d.setScale(2,BigDecimal.ROUND_UP);//保留2位小数，向上取整
           f = d.setScale(2,BigDecimal.ROUND_HALF_DOWN);//保留2位小数，四舍五入，正好.5舍去
           f = d.setScale(2,BigDecimal.ROUND_HALF_UP);//保留2位小数，四舍五入，正好.5进位
       }
   }
}

参考二：

import java.util.*;
import java.io.BufferedInputStream;
import java.math.*;
public class Main {
            
	
	static int N = 2005;
    static BigInteger mod = new BigInteger("1000000007");
    static int n;
    static BigInteger[] a = new BigInteger[N];
    static BigInteger[] dp = new BigInteger[N];
	public static void main(String args[]) {
            
		Scanner cin = new Scanner(System.in);
		int T;
		BigInteger a = new BigInteger("123456789") ;	// 声明BigInteger对象
		BigInteger b = new BigInteger("987654321") ;	// 声明BigInteger对象
		System.out.println("加法操作：" + b.add(a)) ;	// 加法操作
		System.out.println("减法操作：" + b.subtract(a)) ;	// 减法操作
		System.out.println("乘法操作：" + b.multiply(a)) ;	// 乘法操作
		System.out.println("除法操作：" + b.divide(a)) ;	// 除法操作
		System.out.println("最大数：" + b.max(a)) ;	 // 求出最大数
		System.out.println("最小数：" + b.min(a)) ;	 // 求出最小数
		System.out.println("商："+b.divide(a));//求商
		System.out.println("余数"+b.mod(a));//求余数
		BigInteger result[] = b.divideAndRemainder(a) ;	// 求出余数的除法操作
		System.out.println("商是：" + result[0] + 
			"；余数是：" + result[1]) ;
		
		//比较函数
		if( a.compareTo(b) == 0 ) System.out.println("a == b"); //大整数a==b
		else if( a.compareTo(b) > 0 ) System.out.println("a > b"); //大整数a>b
		else if( a.compareTo(b) < 0 ) System.out.println("a < b"); //大整数a<b
		
		int n;
		BigInteger m;
		n=cin.nextInt(); //读入一个int;
		m=cin.nextBigInteger();//读入一个BigInteger;
		m=BigInteger.valueOf(n);//将n转换成大整数
	}
}
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
            
    public static void main(String args[]) {
            
        // read
        Scanner in = new Scanner(System.in);
        BigInteger a = in.nextBigInteger();
 
        // 3 special numbers
        a = BigInteger.ZERO;
        a = BigInteger.ONE;
        a = BigInteger.TEN;
 
        // convert an int to BigInteger
        BigInteger b = BigInteger.valueOf(2333);
        BigInteger p = BigInteger.valueOf(998244353);
 
        // convert a BigInteger to int
        int i = b.intValue();
        // convert a BigInteger to long
        long l = b.longValue();
 
        // operations:
        // a + b;                                BigInteger add(BigInteger b);
        a.add(b);
        // a - b;                                BigInteger subtract(BigInteger b);
        a.subtract(b);
        // a * b;                                BigInteger multiply(BigInteger b);
        a.multiply(b);
        // a / b;                                BigInteger divide(BigInteger b);
        a.divide(b);
        // a % b;                                BigInteger mod(BigInteger b);
        a.mod(b);
        // -a;                                   BigInteger negate();
        a.negate();
        // a < 0 ? -1 : (a > 0 ? 1 : 0);         int signum();
        a.signum();
        // signum(a - b);                        int compareTo(BigInteger b);
        a.compareTo(b);
        // a == b;                               boolean equals(BigInteger b);
        a.equals(b);
 
        // abs(a);                               BigInteger abs();
        a.abs();
        // max(a, b);                            BigInteger max(BigInteger b);
        a.max(b);
        // min(a, b);                            BigInteger min(BigInteger b);
        a.min(b);
        // gcd(a, b);                            BigInteger gcd(BigInteger b);
        a.gcd(b);
        // pow(a, i);                            BigInteger pow(int i);
        a.pow(i);
 
        // modPow(a, b, p);              BigInteger modPow(BigInteger b, BigInteger p);
        a.modPow(b, p);
        // modPow(a, p - 2, p);                  BigInteger modInverse(BigInteger p);
        a.modInverse(p);
        // isPrime(a); (probability:1 - 0.5^i)  boolean isProbablePrime(int certainty);
        a.isProbablePrime(i);
 
        // a << i;                               BigInteger shiftLeft(int i);
        a.shiftLeft(i);
        // a >> i;                               BigInteger shiftRight(int i);
        a.shiftRight(i);
        // a ^ b;                                BigInteger xor(BigInteger b);
        a.xor(b);
        // a | b;                                BigInteger or(BigInteger b);
        a.or(b);
        // a & b;                                BigInteger and(BigInteger b);
        a.and(b);
        // ~a;                                   BigInteger not();
        a.not();
        // a & ~b;                               BigInteger andNot(BigInteger b);
        a.andNot(b);
 
        // ((a >> i) & 1) == 1;                  BigInteger testBit(int i);
        a.testBit(i);
        // a | (1 << i);                         BigInteger setBit(int i);
        a.setBit(i);
        // a & ~(1 << i);                        BigInteger clearBit(int i);
        a.clearBit(i);
        // a ^ (1 << i);                         BigInteger flipBit(int i);
        a.flipBit(i);
        // a & -a;                               BigInteger getLowerSetBit();
        a.getLowestSetBit();
        // __builtin_popcount(a);                int bitCount();
        a.bitCount();
        // ceil(log2(this < 0 ? -this : this+1)) int bitLength();
        a.bitLength();
    }
} 

Java过题代码：

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
            
	static int mod = 1000;
	static int N = 10005;
	static BigInteger[][] f = new BigInteger[1005][105];
	static BigInteger Cnm(int n,int m) {
            
		for(int i = 0;i<=n;i++) {
            
			f[i][0] = new BigInteger("1");
		}
		for(int i = 1;i<=n;i++) {
            
			for(int j = 1;j<=m && j<=i;j++) {
            
				if(i == j)	f[i][j] = new BigInteger("1");
				else {
            
					f[i][j] = new BigInteger("0");
					f[i][j] = f[i-1][j].add(f[i-1][j-1]);
				}
			}
		}
		return f[n][m];
	}
	static int qmi(int a,int b) {
            
		int res = 1;
		while(b!=0) {
            
			if(b%2 == 1)	res = (int) ((long)res*a%mod);
			a = (int) ((long)a*a%mod);
			b = b/2;
		}
		return res;
	}
	public static void main(String[] args) {
            
		int x,k;
		Scanner cin = new Scanner(System.in);
		k = cin.nextInt();
		x = cin.nextInt();
		x = qmi(x,x);
		System.out.println(Cnm(x-1,k-1));
	}
}

（二）Java快速读入输出模板

import java.io.*;
import java.util.*;
public class Main {
            
    public static void main(String[] args) {
            
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(in, out);
        out.close();
    }
    static class Solver {
            
        public void solve(InputReader in, PrintWriter out) {
            
 			//写执行代码
        }
    }
    static class InputReader {
            
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(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 int nextInt() {
            
            return Integer.parseInt(next());
        }
        public long nextLong() {
            
            return Long.parseLong(next());
        }
    }
}

九、计算几何

（一）基本模板：

参考算法竞赛从入门到进阶

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);  //高精度圆周率
const double eps = 1e-8;       //偏差值
const int maxp = 1010;         //点的数量
int sgn(double x){
              //判断x是否等于0
    if(fabs(x) < eps)  return 0;
    else return x<0?-1:1;
}
int Dcmp(double x, double y){
              //比较两个浮点数：0 相等；-1 小于；1 大于
    if(fabs(x - y) < eps) return 0;
    else return x<y ?-1:1;
}
//---------------平面几何：点和线--------
struct Point{
              //定义点和基本运算
    double x,y;
    Point(){
            }
    Point(double x,double y):x(x),y(y){
            }
    Point operator + (Point B){
            return Point(x+B.x,y+B.y);}
    Point operator - (Point B){
            return Point(x-B.x,y-B.y);}
    Point operator * (double k){
            return Point(x*k,y*k);}    //长度增大k倍
    Point operator / (double k){
            return Point(x/k,y/k);}    //长度缩小k倍
    bool operator == (Point B){
            return sgn(x-B.x)==0 && sgn(y-B.y)==0;}
    bool operator < (Point B){
            return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);} //用于凸包
};
typedef Point Vector;   //定义向量
//点积
double Dot(Vector A,Vector B){
            return A.x*B.x + A.y*B.y;}
//向量的长度
double Len(Vector A){
            return sqrt(Dot(A,A));}   
//向量长度的平方
double Len2(Vector A){
            return Dot(A,A);}
//求向量A和B的夹角
double Angle(Vector A,Vector B){
            return acos(Dot(A,B)/Len(A)/Len(B));}
//叉积，大于0则B在A的逆时针方向；小于0则B在A的顺时针方向;等于0则B与A共线，可能是同方向的，也可能是反方向的
double Cross(Vector A,Vector B){
            return A.x*B.y - A.y*B.x;}
//三角形ABC面积的2倍
double Area2(Point A, Point B, Point C){
            return Cross(B-A, C-A);} 
//两点的距离，方法一
double Distance(Point A, Point B){
            return hypot(A.x-B.x,A.y-B.y);} 
//两点的距离，方法二
double Dist(Point A,Point B){
            return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));}
//向量A的单位法向量
Vector Normal(Vector A){
            return Vector(-A.y/ Len(A), A.x/ Len(A));}

bool Parallel(Vector A, Vector B){
            return sgn(Cross(A,B)) == 0;}//向量平行或重合

//向量A逆时针旋转rad度
Vector Rotate(Vector A, double rad){
              
    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}

struct Line{
            
    Point p1,p2;//线上的两个点
    Line(){
            }
    Line(Point p1,Point p2):p1(p1),p2(p2){
            }
   // Line(Point x,Point y){p1 = x;p2 = y;}
  //  Point(double x,double y):x(x),y(y){}
//根据一个点和倾斜角 angle 确定直线,0<=angle<pi
    Line(Point p,double angle){
            
        p1 = p;
        if(sgn(angle - pi/2) == 0){
            p2 = (p1 + Point(0,1));}
        else{
            p2 = (p1 + Point(1,tan(angle)));}
    }
//ax+by+c=0
    Line(double a,double b,double c){
            
        if(sgn(a) == 0){
            
            p1 = Point(0,-c/b);
            p2 = Point(1,-c/b);
        }
        else if(sgn(b) == 0){
            
            p1 = Point(-c/a,0);
            p2 = Point(-c/a,1);
        }
        else{
            
            p1 = Point(0,-c/b);
            p2 = Point(1,(-c-a)/b);
        }
    }
};

typedef Line Segment;   //定义线段，两端点是Point p1,p2

//返回直线倾斜角 0<=angle<pi
double Line_angle(Line v){
            
    double k = atan2(v.p2.y-v.p1.y, v.p2.x-v.p1.x);
    if(sgn(k) < 0)k += pi;
    if(sgn(k-pi) == 0)k -= pi;
        return k;
}
//点和直线关系:1 在左侧;2 在右侧;0 在直线上
int Point_line_relation(Point p,Line v){
            
    int c = sgn(Cross(p-v.p1,v.p2-v.p1));
    if(c < 0)return 1;       //1：p在v的左边
    if(c > 0)return 2;       //2：p在v的右边
    return 0;                //0：p在v上
}
// 点和线段的关系：0 点p不在线段v上；1 点p在线段v上。
bool Point_on_seg(Point p, Line v){
            
    return sgn(Cross(p-v.p1, v.p2-v.p1)) == 0 && sgn(Dot(p - v.p1,p- v.p2)) <= 0;
}

//两直线关系:0 平行,1 重合,2 相交
int Line_relation(Line v1, Line v2){
            
    if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1)) == 0){
            
       if(Point_line_relation(v1.p1,v2)==0)  return 1;//1 重合
       else return 0;//0 平行
    }
    return 2; //2 相交
}

 //点到直线的距离
 double Dis_point_line(Point p, Line v){
            
    return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
 }

//求在直线上的投影点
Point Point_line_proj(Point p, Line v){
            
    double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*k;
}

//点p对直线v的对称点
Point Point_line_symmetry(Point p, Line v){
            
    Point q = Point_line_proj(p,v);//先求点p在直线v的投影点
    return Point(2*q.x-p.x,2*q.y-p.y);
}

//点到线段的距离
double Dis_point_seg(Point p, Segment v){
            
    if(sgn(Dot(p- v.p1,v.p2-v.p1))<0 || sgn(Dot(p- v.p2,v.p1-v.p2))<0) //点的投影不在线段上
        return min(Distance(p,v.p1),Distance(p,v.p2));//到两端点的距离取最小值
    return Dis_point_line(p,v); //点的投影在线段上
 }

//求两直线ab和cd的交点
//**调用前要保证两直线不平行或重合，先判断两直线是否平行
 Point Cross_point(Point a,Point b,Point c,Point d){
             //Line1:ab,  Line2:cd
    double s1 = Cross(b-a,c-a);
    double s2 = Cross(b-a,d-a);  //叉积有正负
    return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
 }

 //两线段是否相交：1 相交，0不相交
 //如果求两线段交点，先判断两线段是否相交，相交则转化成两直线求交点
bool Cross_segment(Point a,Point b,Point c,Point d){
            //Line1:ab,  Line2:cd
	double c1=Cross(b-a,c-a),c2=Cross(b-a,d-a);
	double d1=Cross(d-c,a-c),d2=Cross(d-c,b-c);
	return sgn(c1)*sgn(c2)<0 && sgn(d1)*sgn(d2)<0;//注意交点是端点的情况不算在内
}

//---------------平面几何：多边形----------------
struct Polygon{
            
    int n;   //多边形的顶点数
    Point p[maxp];   //多边形的点
    Line v[maxp];    //多边形的边
};

//判断点和任意多边形的关系: 3 点上; 2 边上; 1 内部; 0 外部
//点pt，多边形的点Point *p，多边形点的数量n，多边形顶点按照顺时针或者逆时针方向排列
int Point_in_polygon(Point pt,Point *p,int n){
             
    for(int i = 0;i < n;i++){
              //点在多边形的顶点上,下标从0开始
        if(p[i] == pt)return 3;
    }
    for(int i = 0;i < n;i++){
            //点在多边形的边上
        Line v=Line(p[i],p[(i+1)%n]);
        if(Point_on_seg(pt,v)) return 2;
    }
    int num = 0;
    for(int i = 0;i < n;i++){
            
        int j = (i+1)% n;
        int c = sgn(Cross(pt-p[j],p[i]-p[j]));
        int u = sgn(p[i].y - pt.y);
        int v = sgn(p[j].y - pt.y);
        if(c > 0 && u < 0 && v >=0) num++;
        if(c < 0 && u >=0 && v < 0) num--;
    }
    return num != 0; //1 内部; 0 外部
}

//求多边形的面积，从原点开始划分三角形，顶点按照顺时针或者逆时针方向排列
double Polygon_area(Point *p, int n){
             //Point *p表示多边形。
    double area = 0;
    for(int i = 0;i < n;i++)
        area += Cross(p[i],p[(i+1)%n]);
    return area/2;    //面积有正负，不能简单地取绝对值
}
//求多边形重心。Point *p表示多边形。
Point Polygon_center(Point *p, int n){
             
    Point ans(0,0);
    if(Polygon_area(p,n)==0) return ans;
    for(int i = 0;i < n;i++)
        ans = ans + (p[i]+p[(i+1)%n]) * Cross(p[i],p[(i+1)%n]); //面积有正负
    return ans/Polygon_area(p,n)/6.;
}

//Convex_hull()求凸包。凸包顶点放在ch中，返回值是凸包的顶点数
int Convex_hull(Point *p,int n,Point *ch){
            
    sort(p,p+n);         //对点排序：按x从小到大排序，如果x相同，按y排序
    n=unique(p,p+n)-p;   //去除重复点
    int v=0;
	//求下凸包。如果p[i]是右拐弯的，这个点不在凸包上，往回退
    for(int i=0;i<n;i++){
            
        while(v>1 && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
			v--;
        ch[v++]=p[i];
    }
    int j=v;
	//求上凸包
    for(int i=n-2;i>=0;i--){
            
        while(v>j && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
			v--;
        ch[v++]=p[i];
    }
    if(n>1) v--;
    return v;   //返回值v是凸包的顶点数
}

//---------------平面几何：圆----------------
struct Circle{
            
    Point c;//圆心
    double r;//半径
    Circle(){
            }
    Circle(Point c,double r):c(c),r(r){
            }
    Circle(double x,double y,double _r){
            c=Point(x,y);r = _r;}
};

//点和圆的关系: 0 点在圆内, 1 圆上, 2 圆外.
int Point_circle_relation(Point p, Circle C){
            
    double dst = Distance(p,C.c);
    if(sgn(dst - C.r) < 0) return 0;  //点在圆内
    if(sgn(dst - C.r) ==0) return 1;   //圆上
    return 2;   //圆外
}

//直线和圆的关系：0 直线在圆内, 1 直线和圆相切, 2 直线在圆外
int Line_circle_relation(Line v,Circle C){
            
    double dst = Dis_point_line(C.c,v);
    if(sgn(dst-C.r) < 0) return 0; //直线在圆内
    if(sgn(dst-C.r) ==0) return 1;  //直线和圆相切
    return 2; //直线在圆外
}

//线段和圆的关系：0 线段在圆内, 1 线段和圆相切, 2 线段在圆外
int Seg_circle_relation(Segment v,Circle C){
            
    double dst = Dis_point_seg(C.c,v);
    if(sgn(dst-C.r) < 0) return 0; //线段在圆内
    if(sgn(dst-C.r) ==0) return 1;  //线段和圆相切
    return 2;    //线段在圆外
}

//直线和圆的交点，pa, pb是交点。返回值是交点个数
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
            
    if(Line_circle_relation(v, C)==2) return 0;//无交点
    Point q = Point_line_proj(C.c,v);  //圆心在直线上的投影点
    double d = Dis_point_line(C.c,v);   //圆心到直线的距离
    double k = sqrt(C.r*C.r-d*d);   //
    if(sgn(k) == 0){
               //1个交点，直线和圆相切
        pa = q;
        pb = q;
        return 1;
    }
    Point n=(v.p2-v.p1)/ Len(v.p2-v.p1);  //单位向量
    pa = q + n*k;
    pb = q - n*k;
    return 2;//2个交点
}

//-------------------三维几何----------------
//三维：点
struct Point3{
            
    double x,y,z;
    Point3(){
            }
    Point3(double x,double y,double z):x(x),y(y),z(z){
            }
    Point3 operator + (Point3 B){
            return Point3(x+B.x,y+B.y,z+B.z);}
    Point3 operator - (Point3 B){
            return Point3(x-B.x,y-B.y,z-B.z);}
    Point3 operator * (double k){
            return Point3(x*k,y*k,z*k);}
    Point3 operator / (double k){
            return Point3(x/k,y/k,z/k);}
    bool operator == (Point3 B){
            return sgn(x-B.x)==0 && sgn(y-B.y)==0 && sgn(z-B.z)==0;}
};
typedef Point3 Vector3;
//点积。和二维点积函数同名。C++允许函数同名。
double Dot(Vector3 A,Vector3 B){
            return A.x*B.x+A.y*B.y+A.z*B.z;}
//叉积
Vector3 Cross(Vector3 A,Vector3 B){
            return Point3(A.y*B.z-A.z*B.y,A.z*B.x-A.x*B.z,A.x*B.y-A.y*B.x);}
double Len(Vector3 A){
            return sqrt(Dot(A,A));}   //向量的长度
double Len2(Vector3 A){
            return Dot(A,A);}        //向量长度的平方
double Distance(Point3 A,Point3 B){
            
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+(A.z-B.z)*(A.z-B.z));
}
double Angle(Vector3 A,Vector3 B){
            return acos(Dot(A,B)/Len(A)/Len(B));}   //A与B的夹角
//三维：线
struct Line3{
            
    Point3 p1,p2;
    Line3(){
            }
    Line3(Point3 p1,Point3 p2):p1(p1),p2(p2){
            }
};
typedef Line3 Segment3;   //定义线段，两端点是Point p1,p2

//三角形面积的2倍
double Area2(Point3 A,Point3 B,Point3 C){
            return Len(Cross(B-A, C-A));}

//三维：点到直线距离
double Dis_point_line(Point3 p, Line3 v){
            
    return Len(Cross(v.p2-v.p1,p-v.p1))/Distance(v.p1,v.p2);
}

//三维：点在直线上
bool Point_line_relation(Point3 p,Line3 v){
            
    return sgn( Len(Cross(v.p1-p,v.p2-p))) == 0 && sgn(Dot(v.p1-p,v.p2-p))== 0;
}
//三维：点到线段距离。
double Dis_point_seg(Point3 p, Segment3 v){
            
    if(sgn(Dot(p- v.p1,v.p2-v.p1)) < 0 || sgn(Dot(p- v.p2,v.p1-v.p2)) < 0)
        return min(Distance(p,v.p1),Distance(p,v.p2));
    return Dis_point_line(p,v);
}
//三维：点 p 在直线上的投影
Point3 Point_line_proj(Point3 p, Line3 v){
            
    double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*k;
}
//三维：平面
struct Plane{
            
    Point3 p1,p2,p3;//平面上的三个点
    Plane(){
            }
    Plane(Point3 p1,Point3 p2,Point3 p3):p1(p1),p2(p2),p3(p3){
            }
};
//平面法向量
Point3 Pvec(Point3 A,Point3 B,Point3 C){
             return Cross(B-A,C-A);}
Point3 Pvec(Plane f){
             return Cross(f.p2-f.p1,f.p3-f.p1);}
//四点共平面
bool Point_on_plane(Point3 A,Point3 B,Point3 C,Point3 D){
            
    return sgn(Dot(Pvec(A,B,C),D-A)) == 0;
}
//两平面平行
int Parallel(Plane f1, Plane f2){
            
    return Len(Cross(Pvec(f1),Pvec(f2))) < eps;
}
//两平面垂直
int Vertical (Plane f1, Plane f2){
            
    return sgn(Dot(Pvec(f1),Pvec(f2)))==0;
}
//直线与平面的交点p，返回值是交点个数  
int Line_cross_plane(Line3 u,Plane f,Point3 &p){
            
    Point3 v = Pvec(f);
    double x = Dot(v, u.p2-f.p1);
    double y = Dot(v, u.p1-f.p1);
    double d = x-y;
    if(sgn(x) == 0 && sgn(y) == 0) return -1;//-1：v在f上
    if(sgn(d) == 0)return 0;                  //0：v与f平行
    p = ((u.p1 * x)-(u.p2 * y))/d;             //v与f相交
    return 1;
}

//四面体有向体积*6
double volume4(Point3 A,Point3 B,Point3 C,Point3 D){
            return Dot(Cross(B-A,C-A),D-A);}


int main(){
            
    Point a(0,1),b(0,0),c(1,1),d(1,2),p(1.5,1);
    double a1=5,b1=6,c1=1;
    Line k(a,b),k2(c,d);
    Point pr(1,1),cr(1,1); double r=1; Circle C(cr,r);

    cout<<endl<<"Line_circle_relation="<<Line_circle_relation(k,C);
    cout<<endl<<"Seg_circle_relation="<<Seg_circle_relation(k,C);
    cout<<endl<<"Point_circle_relation="<<Point_circle_relation(pr,C);
    cout<<endl<<"parallel="<<Parallel(a,b)<<endl;
    cout<<"dot="<<Dot(a,b)<<endl<<" angle="<<Angle(a,b)<<endl;
    cout<<"90:"<<sgn(Rotate(a, -pi/2).x)<<endl<<Rotate(a, -pi/2).y;
    cout<<endl<<"line angle="<<Line_angle(k)*4;
    cout<<endl<<"line place="<<Point_line_relation(p,k);
    cout<<endl<<"point_on_seg="<<Point_on_seg(p,k);
    cout<<endl<<"dis_point_line="<<Dis_point_line(p,k);
    cout<<endl<<"dis_point_line="<<Dis_point_seg(p,k);
    Point pp=Cross_point(a,b,c,d);
    cout<<endl<<"crosspoint="<<pp.x<<"  "<<pp.y;
    cout<<endl<<"cross seg="<<Cross_segment(a,b,c,d);
    cout<<endl<<"distance="<<Distance(a,b);
    cout<<endl<<"line_relation="<<Line_relation(k,k2);
    Point g[4];
    g[0]=a;g[1]=b;g[2]=c;g[3]=d;
    cout<<endl<<"Point_in_polygon="<<Point_in_polygon(p,g,4);
    cout<<endl<<"Polygon_area="<<Polygon_area(g,4);
    cout<<endl<<endl;
	return 0;
}

（二）求半平面交

1.点向式求半平面交

import java.util.*;

class Point {
            
    double x, y;

    Point() {
            }

    Point(double x, double y) {
            
        this.x = x;
        this.y = y;
    }

    Point add(Point B) {
            
        return new Point(x + B.x, y + B.y);
    }

    Point subtract(Point B) {
            
        return new Point(x - B.x, y - B.y);
    }

    Point multiply(double k) {
            
        return new Point(x * k, y * k);
    }
}

class Vector extends Point {
            
    Vector(double x, double y) {
            
        super(x, y);
    }
}

class Line {
            
    Point p;
    Vector v;
    double ang;

    Line(Point p, Vector v) {
            
        this.p = p;
        this.v = v;
        ang = Math.atan2(v.y, v.x);
    }
}

public class HalfPlaneIntersectionPointVector {
            
    static final double INF = 1e12;
    static final double EPS = 1e-8;

    static int sgn(double x) {
            
        if (Math.abs(x) < EPS) return 0;
        else return x < 0 ? -1 : 1;
    }

    static double cross(Vector A, Vector B) {
            
        return A.x * B.y - A.y * B.x;
    }

    static boolean onLeft(Line L, Point p) {
            
        return sgn(cross(L.v, p.subtract(L.p))) > 0;
    }

    static Point crossPoint(Line a, Line b) {
            
        Vector u = a.p.subtract(b.p);
        double t = cross(b.v, u) / cross(a.v, b.v);
        return a.p.add(a.v.multiply(t));
    }

    static List<Point> HPI(List<Line> L) {
            
        int n = L.size();
        L.sort(Comparator.comparingDouble(o -> o.ang));

        Deque<Line> q = new ArrayDeque<>();
        List<Point> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            
            while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();
            while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getFirst(), q.get(1)))) q.removeFirst();
            q.addLast(L.get(i));

            if (q.size() > 1)
                ans.set(ans.size() - 1, crossPoint(q.getLast(), q.get(q.size() - 2)));
        }

        while (q.size() > 2 && !onLeft(q.getFirst(), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();

        if (q.size() <= 2) return new ArrayList<>();
        ans.add(crossPoint(q.getLast(), q.getFirst()));

        return ans;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            
            int n = sc.nextInt();
            List<Line> L = new ArrayList<>();
            L.add(new Line(new Point(0, 0), new Vector(0, -1)));
            L.add(new Line(new Point(0, INF), new Vector(-1, 0)));

            for (int i = 0; i < n; i++) {
            
                double a = sc.nextDouble(), b = sc.nextDouble();
                L.add(new Line(new Point(0, a), new Vector(1, b)));
            }

            List<Point> ans = HPI(L);
            System.out.println(ans.size() - 2);
        }
    }
}

2.两点式求半平面交一

import java.util.*;

class Point {
            
    double x, y;

    Point() {
            }

    Point(double x, double y) {
            
        this.x = x;
        this.y = y;
    }

    Point add(Point B) {
            
        return new Point(x + B.x, y + B.y);
    }

    Point subtract(Point B) {
            
        return new Point(x - B.x, y - B.y);
    }

    Point multiply(double k) {
            
        return new Point(x * k, y * k);
    }

    Point divide(double k) {
            
        return new Point(x / k, y / k);
    }
}

class Line {
            
    Point p1, p2;

    Line(Point p1, Point p2) {
            
        this.p1 = p1;
        this.p2 = p2;
    }
}

public class HalfPlaneIntersectionTwoPoints {
            
    static final double INF = 1e12;
    static final double EPS = 1e-8;

    static int sgn(double x) {
            
        if (Math.abs(x) < EPS) return 0;
        else return x < 0 ? -1 : 1;
    }

    static double dot(Point A, Point B) {
            
        return A.x * B.x + A.y * B.y;
    }

    static double dist(Point A, Point B) {
            
        return Math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
    }

    static double cross(Point A, Point B) {
            
        return A.x * B.y - A.y * B.x;
    }

    static double area2(Point A, Point B, Point C) {
            
        return cross(B.subtract(A), C.subtract(A));
    }

    static double getAngle(Line a) {
            
        return Math.atan2(a.p2.y - a.p1.y, a.p2.x - a.p1.x);
    }

    static int pointLineRelation(Point p, Line v) {
            
        int c = sgn(cross(p.subtract(v.p1), v.p2.subtract(v.p1)));
        if (c < 0) return 1; // p在v的左边
        if (c > 0) return 2; // p在v的右边
        return 0; // p在v上
    }

    static Point crossPoint(Point a, Point b, Point c, Point d) {
             // Line1:ab, Line2:cd
        double s1 = cross(b.subtract(a), c.subtract(a));
        double s2 = cross(b.subtract(a), d.subtract(a)); // 叉积有正负
        return new Point((c.x * s2 - d.x * s1) / (s2 - s1), (c.y * s2 - d.y * s1) / (s2 - s1));
    }

    static Point crossPoint(Line a, Line b) {
            
        return crossPoint(a.p1, a.p2, b.p1, b.p2);
    }

    static boolean onLeft(Line l, Point p) {
            
        return pointLineRelation(p, l) == 1;
    }

    static List<Point> HPI(List<Line> L) {
            
        int n = L.size();
        L.sort(Comparator.comparingDouble(HalfPlaneIntersectionTwoPoints::getAngle).thenComparing(l -> -area2(l.p1, l.p2, new Point(INF, INF))));

        Deque<Line> q = new ArrayDeque<>();
        List<Point> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            
            while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();
            while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getFirst(), q.get(1)))) q.removeFirst();
            q.addLast(L.get(i));

            if (q.size() > 1)
                ans.set(ans.size() - 1, crossPoint(q.getLast(), q.get(q.size() - 2)));
        }

        while (q.size() > 2 && !onLeft(q.getFirst(), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();

        if (q.size() <= 2) return new ArrayList<>();
        ans.add(crossPoint(q.getLast(), q.getFirst()));

        return ans;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            
            int n = sc.nextInt();
            List<Line> L = new ArrayList<>();
            L.add(new Line(new Point(0, 0), new Point(0, -1)));
            L.add(new Line(new Point(0, INF), new Point(-1, INF)));

            for (int i = 0; i < n; i++) {
            
                double p = sc.nextDouble(), v = sc.nextDouble();
                L.add(new Line(new Point(0, p), new Point(1, v + p)));
            }

            List<Point> ans = HPI(L);
            System.out.println(ans.size() - 2);
        }
    }
}

3.两点式求半平面交模板二

typedef long long ll;
typedef long double LD;
typedef pair<int,int> PII;
const double inf = 1e12;
const int N = 100005;
const LD eps = 1e-18;
int n,m;
int sgn(double x){
              //判断x是否等于0
    if(fabs(x) < eps)  return 0;
    else return x<0?-1:1;
}
int Dcmp(double x, double y){
              //比较两个浮点数：0 相等；-1 小于；1 大于
    if(fabs(x - y) < eps) return 0;
    else return x<y ?-1:1;
}
struct Point{
              //定义点和基本运算
    double x,y;
    Point(){
            }
    Point(double x,double y):x(x),y(y){
            }
    Point operator + (Point B){
            return Point(x+B.x,y+B.y);}
    Point operator - (Point B){
            return Point(x-B.x,y-B.y);}
    Point operator * (double k){
            return Point(x*k,y*k);}    //长度增大k倍
    Point operator / (double k){
            return Point(x/k,y/k);}    //长度缩小k倍
    bool operator == (Point B){
            return sgn(x-B.x)==0 && sgn(y-B.y)==0;}
    bool operator < (Point B){
            return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);} //用于凸包
};
typedef Point Vector;   //定义向量
double Cross(Vector A,Vector B){
            return A.x*B.y - A.y*B.x;}
double Area2(Point A, Point B, Point C){
            return Cross(B-A, C-A);} 
struct Line{
            
    Point p1,p2;//线上的两个点
    Line(){
            }
    Line(Point p1,Point p2):p1(p1),p2(p2){
            }
};
Line line[N];
int cnt;
int q[N];//定义双端队列
double get_angle(Line a) {
            
	return atan2(a.p2.y-a.p1.y,a.p2.x-a.p1.x);
}
//排序：极角小的排前面，极角相同时，最左边的排在最后面，以便去重
bool cmp(Line a, Line b) {
            
  double A =  get_angle(a), B = get_angle(b);
  if (fabs(A - B) < eps) return Area2(a.p1,a.p2,b.p2)<0;
  return A < B;
}
Point Cross_point(Point a,Point b,Point c,Point d){
             //Line1:ab,  Line2:cd
	double s1 = Cross(b-a,c-a);
	double s2 = Cross(b-a,d-a);  //叉积有正负
    return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}
//两直线交点
Point Cross_point(Line a,Line b){
                
    return Cross_point(a.p1,a.p2,b.p1,b.p2);
}
// 判断bc的交点是否在a的右侧
bool on_right(Line a, Line b, Line c){
            
    Point o = Cross_point(b, c);
    //如果删除重合的点加上等号 
    return Area2(a.p1, a.p2, o) <= 0;
}
vector<Point> HPI(vector<Line> L){
            
	int cnt = L.size();
    sort(L.begin(),L.end(), cmp);
    int l = 0, r = -1;//头部和尾部 
    for (int i = 0; i < cnt; i ++ ){
            
        if (i && !Dcmp(get_angle(L[i - 1]), get_angle(L[i]))) continue;
        while (l + 1 <= r && on_right(L[i], L[q[r - 1]], L[q[r]])) r -- ;
        while (l + 1 <= r && on_right(L[i], L[q[l]], L[q[l + 1]])) l ++ ;
        q[ ++ r] = i;
    }
    while (l + 1 <= r && on_right(L[q[l]], L[q[r - 1]], L[q[r]])) r -- ;
    while (l + 1 <= r && on_right(L[q[r]], L[q[l]], L[q[l + 1]])) l ++ ;
    int k = 0;
    vector<Point> ans;
    if(r - l <= 1)	return ans;//返回空集 
    q[++r] = q[l];//将头部的直线加入尾部 
    for(int i = l;i<r;i++){
            
    	ans.push_back(Cross_point(L[q[i]],L[q[i+1]]));
	}
    return ans;
}
double Polygon_area(vector<Point> p){
             //Point *p表示多边形。
    double area = 0;
    int n = p.size();
    for(int i = 0;i < n;i++)
        area += Cross(p[i],p[(i+1)%n]);
    return area/2;    //面积有正负，不能简单地取绝对值
}

vector<Line> L;
vector<Point> ans;
Point pg[N];
int main(){
            
	int i,j,T;
	cin>>T;
	while(T--){
            
		int n;
		L.clear();
		cin>>n;
		for(i = 1;i<=n;i++){
            
			double p,v;
			scanf("%lf %lf",&p,&v);
			Line l(Point(0,p),Point(1,v+p));
			L.push_back(l);
		}
		//加入两个边界的直线
		L.push_back(Line(Point(0,0),Point(0,-1)));
		L.push_back(Line(Point(0,inf),Point(-1,inf)));
		vector<Point> ans = HPI(L);
		cout<<ans.size()-2<<endl;
	} 
	return 0;
} 

（三）模拟退火求最小球覆盖

import java.util.Scanner;

public class MinimumEnclosingSphere_SA {
            

    // 点类，表示三维空间中的点
    static class Point {
            
        double x, y, z;

        public Point(double x, double y, double z) {
            
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    // 常量定义
    static final int MAXN = 105;           // 最多点数
    static final double EPS = 1e-8;         // 精度控制
    static Point[] dots = new Point[MAXN]; // 存储所有点

    // 计算两点之间的欧几里得距离
    static double distance(Point a, Point b) {
            
        return Math.sqrt(
            (a.x - b.x) * (a.x - b.x) +
            (a.y - b.y) * (a.y - b.y) +
            (a.z - b.z) * (a.z - b.z)
        );
    }

    // 模拟退火主函数：寻找最小包围球的半径
    static double solve(int n) {
            
        double step = 200;      // 初始步长（越大搜索范围越广）
        double ans = 1e9;       // 初始答案设为极大值
        Point center = new Point(0, 0, 0); // 当前球心位置
        int farthestIndex = 0;  // 当前离球心最远的点索引

        // 模拟退火过程
        while (step > EPS) {
            
            // 找出当前球心离得最远的点
            farthestIndex = 0;
            for (int i = 1; i <= n; i++) {
            
                if (distance(center, dots[i]) > distance(center, dots[farthestIndex])) {
            
                    farthestIndex = i;
                }
            }

            // 计算当前球心到该最远点的距离（即当前半径）
            double currentRadius = distance(center, dots[farthestIndex]);
            ans = Math.min(ans, currentRadius); // 更新最小半径

            // 向该点方向移动球心，移动幅度与当前步长有关
            center.x += (dots[farthestIndex].x - center.x) / currentRadius * step;
            center.y += (dots[farthestIndex].y - center.y) / currentRadius * step;
            center.z += (dots[farthestIndex].z - center.z) / currentRadius * step;

            // 温度下降（步长逐渐减小）
            step *= 0.9999; // 步长衰减因子，接近于1，收敛更稳定
        }

        return ans;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            double z = sc.nextDouble();
            dots[i] = new Point(x, y, z);
        }

        double result = solve(n);

        // 输出结果，保留7位小数
        System.out.printf("%.7f
", result);
    }
}

Point c, Point d) { // Line1:ab, Line2:cd
double s1 = cross(b.subtract(a), c.subtract(a));
double s2 = cross(b.subtract(a), d.subtract(a)); // 叉积有正负
return new Point((c.x * s2 – d.x * s1) / (s2 – s1), (c.y * s2 – d.y * s1) / (s2 – s1));
}

static Point crossPoint(Line a, Line b) {
    return crossPoint(a.p1, a.p2, b.p1, b.p2);
}

static boolean onLeft(Line l, Point p) {
    return pointLineRelation(p, l) == 1;
}

static List<Point> HPI(List<Line> L) {
    int n = L.size();
    L.sort(Comparator.comparingDouble(HalfPlaneIntersectionTwoPoints::getAngle).thenComparing(l -> -area2(l.p1, l.p2, new Point(INF, INF))));

    Deque<Line> q = new ArrayDeque<>();
    List<Point> ans = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();
        while (q.size() > 1 && !onLeft(L.get(i), crossPoint(q.getFirst(), q.get(1)))) q.removeFirst();
        q.addLast(L.get(i));

        if (q.size() > 1)
            ans.set(ans.size() - 1, crossPoint(q.getLast(), q.get(q.size() - 2)));
    }

    while (q.size() > 2 && !onLeft(q.getFirst(), crossPoint(q.getLast(), q.get(q.size() - 2)))) q.removeLast();

    if (q.size() <= 2) return new ArrayList<>();
    ans.add(crossPoint(q.getLast(), q.getFirst()));

    return ans;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while (T-- > 0) {
        int n = sc.nextInt();
        List<Line> L = new ArrayList<>();
        L.add(new Line(new Point(0, 0), new Point(0, -1)));
        L.add(new Line(new Point(0, INF), new Point(-1, INF)));

        for (int i = 0; i < n; i++) {
            double p = sc.nextDouble(), v = sc.nextDouble();
            L.add(new Line(new Point(0, p), new Point(1, v + p)));
        }

        List<Point> ans = HPI(L);
        System.out.println(ans.size() - 2);
    }
}

}

#### 3.两点式求半平面交模板二

```cpp
typedef long long ll;
typedef long double LD;
typedef pair<int,int> PII;
const double inf = 1e12;
const int N = 100005;
const LD eps = 1e-18;
int n,m;
int sgn(double x){  //判断x是否等于0
    if(fabs(x) < eps)  return 0;
    else return x<0?-1:1;
}
int Dcmp(double x, double y){  //比较两个浮点数：0 相等；-1 小于；1 大于
    if(fabs(x - y) < eps) return 0;
    else return x<y ?-1:1;
}
struct Point{  //定义点和基本运算
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x+B.x,y+B.y);}
    Point operator - (Point B){return Point(x-B.x,y-B.y);}
    Point operator * (double k){return Point(x*k,y*k);}    //长度增大k倍
    Point operator / (double k){return Point(x/k,y/k);}    //长度缩小k倍
    bool operator == (Point B){return sgn(x-B.x)==0 && sgn(y-B.y)==0;}
    bool operator < (Point B){return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);} //用于凸包
};
typedef Point Vector;   //定义向量
double Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}
double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} 
struct Line{
    Point p1,p2;//线上的两个点
    Line(){}
    Line(Point p1,Point p2):p1(p1),p2(p2){}
};
Line line[N];
int cnt;
int q[N];//定义双端队列
double get_angle(Line a) {
	return atan2(a.p2.y-a.p1.y,a.p2.x-a.p1.x);
}
//排序：极角小的排前面，极角相同时，最左边的排在最后面，以便去重
bool cmp(Line a, Line b) {
  double A =  get_angle(a), B = get_angle(b);
  if (fabs(A - B) < eps) return Area2(a.p1,a.p2,b.p2)<0;
  return A < B;
}
Point Cross_point(Point a,Point b,Point c,Point d){ //Line1:ab,  Line2:cd
	double s1 = Cross(b-a,c-a);
	double s2 = Cross(b-a,d-a);  //叉积有正负
    return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}
//两直线交点
Point Cross_point(Line a,Line b){    
    return Cross_point(a.p1,a.p2,b.p1,b.p2);
}
// 判断bc的交点是否在a的右侧
bool on_right(Line a, Line b, Line c){
    Point o = Cross_point(b, c);
    //如果删除重合的点加上等号 
    return Area2(a.p1, a.p2, o) <= 0;
}
vector<Point> HPI(vector<Line> L){
	int cnt = L.size();
    sort(L.begin(),L.end(), cmp);
    int l = 0, r = -1;//头部和尾部 
    for (int i = 0; i < cnt; i ++ ){
        if (i && !Dcmp(get_angle(L[i - 1]), get_angle(L[i]))) continue;
        while (l + 1 <= r && on_right(L[i], L[q[r - 1]], L[q[r]])) r -- ;
        while (l + 1 <= r && on_right(L[i], L[q[l]], L[q[l + 1]])) l ++ ;
        q[ ++ r] = i;
    }
    while (l + 1 <= r && on_right(L[q[l]], L[q[r - 1]], L[q[r]])) r -- ;
    while (l + 1 <= r && on_right(L[q[r]], L[q[l]], L[q[l + 1]])) l ++ ;
    int k = 0;
    vector<Point> ans;
    if(r - l <= 1)	return ans;//返回空集 
    q[++r] = q[l];//将头部的直线加入尾部 
    for(int i = l;i<r;i++){
    	ans.push_back(Cross_point(L[q[i]],L[q[i+1]]));
	}
    return ans;
}
double Polygon_area(vector<Point> p){ //Point *p表示多边形。
    double area = 0;
    int n = p.size();
    for(int i = 0;i < n;i++)
        area += Cross(p[i],p[(i+1)%n]);
    return area/2;    //面积有正负，不能简单地取绝对值
}

vector<Line> L;
vector<Point> ans;
Point pg[N];
int main(){
	int i,j,T;
	cin>>T;
	while(T--){
		int n;
		L.clear();
		cin>>n;
		for(i = 1;i<=n;i++){
			double p,v;
			scanf("%lf %lf",&p,&v);
			Line l(Point(0,p),Point(1,v+p));
			L.push_back(l);
		}
		//加入两个边界的直线
		L.push_back(Line(Point(0,0),Point(0,-1)));
		L.push_back(Line(Point(0,inf),Point(-1,inf)));
		vector<Point> ans = HPI(L);
		cout<<ans.size()-2<<endl;
	} 
	return 0;
} 

（三）模拟退火求最小球覆盖

import java.util.Scanner;

public class MinimumEnclosingSphere_SA {
            

    // 点类，表示三维空间中的点
    static class Point {
            
        double x, y, z;

        public Point(double x, double y, double z) {
            
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    // 常量定义
    static final int MAXN = 105;           // 最多点数
    static final double EPS = 1e-8;         // 精度控制
    static Point[] dots = new Point[MAXN]; // 存储所有点

    // 计算两点之间的欧几里得距离
    static double distance(Point a, Point b) {
            
        return Math.sqrt(
            (a.x - b.x) * (a.x - b.x) +
            (a.y - b.y) * (a.y - b.y) +
            (a.z - b.z) * (a.z - b.z)
        );
    }

    // 模拟退火主函数：寻找最小包围球的半径
    static double solve(int n) {
            
        double step = 200;      // 初始步长（越大搜索范围越广）
        double ans = 1e9;       // 初始答案设为极大值
        Point center = new Point(0, 0, 0); // 当前球心位置
        int farthestIndex = 0;  // 当前离球心最远的点索引

        // 模拟退火过程
        while (step > EPS) {
            
            // 找出当前球心离得最远的点
            farthestIndex = 0;
            for (int i = 1; i <= n; i++) {
            
                if (distance(center, dots[i]) > distance(center, dots[farthestIndex])) {
            
                    farthestIndex = i;
                }
            }

            // 计算当前球心到该最远点的距离（即当前半径）
            double currentRadius = distance(center, dots[farthestIndex]);
            ans = Math.min(ans, currentRadius); // 更新最小半径

            // 向该点方向移动球心，移动幅度与当前步长有关
            center.x += (dots[farthestIndex].x - center.x) / currentRadius * step;
            center.y += (dots[farthestIndex].y - center.y) / currentRadius * step;
            center.z += (dots[farthestIndex].z - center.z) / currentRadius * step;

            // 温度下降（步长逐渐减小）
            step *= 0.9999; // 步长衰减因子，接近于1，收敛更稳定
        }

        return ans;
    }

    public static void main(String[] args) {
            
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            double z = sc.nextDouble();
            dots[i] = new Point(x, y, z);
        }

        double result = solve(n);

        // 输出结果，保留7位小数
        System.out.printf("%.7f
", result);
    }
}