L3-3 神坛(Java)
分数 30a
全屏浏览题目切换布局
作者 邓俊辉
单位 清华大学
在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 0.000。
长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。
输入格式：
输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（−109≤ 横坐标、纵坐标 <109）。
输出格式：
在一行中输出神坛的最小面积，四舍五入保留 3 位小数。
答案
import java.util.Arrays; import java.util.Scanner; public class Main { static class Node { long x, y; int rel; Node(long x, long y) { this.x = x; this.y = y; } } static int n; static Node[] a; static Node[] b; static boolean cmp(Node x, Node y) { if (x.rel != y.rel) { return x.rel < y.rel; } return x.x * y.y - x.y * y.x > 0; } static int judge(Node x) { if (x.x > 0 && x.y > 0) return 1; if (x.x > 0 && x.y < 0) return 2; if (x.x < 0 && x.y < 0) return 3; if (x.x < 0 && x.y > 0) return 4; return 0; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); a = new Node[n + 1]; b = new Node[n + 1]; for (int i = 1; i <= n; i++) { a[i] = new Node(scanner.nextLong(), scanner.nextLong()); } double ans = -1; int cnt; for (int i = 1; i <= n; i++) { cnt = 1; for (int j = 1; j <= n; j++) { if (i == j) { continue; } b[cnt] = new Node(a[j].x - a[i].x, a[j].y - a[i].y); b[cnt].rel = judge(b[cnt]); cnt++; } Arrays.sort(b, 1, n, Main::cmp); for (int j = 1; j < n - 1; j++) { if (ans == -1 || Math.abs(b[j + 1].x * b[j].y - b[j + 1].y * b[j].x) * 0.5 < ans) { ans = Math.abs(b[j + 1].x * b[j].y - b[j + 1].y * b[j].x) * 0.5; } } } System.out.printf("%.3f\n", ans); } }
