首页 > 代码库 > UVa 10213 (欧拉公式+Java大数) How Many Pieces of Land ?
UVa 10213 (欧拉公式+Java大数) How Many Pieces of Land ?
题意：
一块圆形土地，在圆周上选n个点，然后两两连线，问把这块土地分成多少块？
分析：
首先紫书上的公式是错的，不过根据书上提供的思路很容易稍加修改得到正确答案！
然后推公式吧，这里用到平面图的欧拉公式，V - E + F = 2，其中V表示顶点个数，E表示边的个数，F表示面的块数。
减去最外面的无限大的面，所求ans = E - V + 1
假设n≥4，从圆周上的一个点出发枚举一条对角线，左边有i个点，右边有n-2-i个点，将左右两边的点两两相连，就在这条对角线上得到个交点。每个交点被重复计算4次，再加上圆周上的n个点，所以
接下来E也很好计算，一条对角线有个交点，所以就有
条边，而这里要注意，每条边是被重复计算2次的。再加上圆周被n个点分隔开的n条边和n个点相邻两点的连线有n条边，所以
然后再根据这两个公式、
化简一下得到
后来发现，这道题还需要高精度，于是乎我傻乎乎地写了高精度加法和乘法，后来发现还需要除法，除法实在不会写。又想到lw学长整理过Java的BigInteger类的一些相关东西(工具」 Java总结 Version1.0)，于是从没接触过Java的我，从安装Java JDK开始，怒学一下午Java，终于把这道题A了。不说了，我好累，不过也很欣慰。
1 import java.io.*; 2 import java.util.*; 3 import java.math.*; 4 5 public class Main 6 { 7 static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); 8 9 public static void main(String args[]) throws IOException10 {11 Scanner cin=new Scanner(System.in);12 int kase = cin.nextInt();13 for(int c = 1; c <= kase; ++c)14 {15 BigInteger ans = BigInteger.valueOf(1);16 String s = cin.next();17 BigInteger n = new BigInteger(s);18 BigInteger temp = new BigInteger(s);19 //System.out.println("temp = " + temp);20 temp = temp.multiply(temp.subtract(new BigInteger("1")));21 //System.out.println("temp = " + temp);22 temp = temp.divide(new BigInteger("2"));23 //System.out.println("temp = " + temp);24 ans = ans.add(temp);25 temp = temp.multiply(n.subtract(new BigInteger("2")));26 temp = temp.multiply(n.subtract(new BigInteger("3")));27 temp = temp.divide(new BigInteger("12"));28 ans = ans.add(temp);29 System.out.println(ans);30 }31 }32 }
UVa 10213 (欧拉公式+Java大数) How Many Pieces of Land ?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。