HDU 2036 改革春风吹满地
2021-11-29 本文已影响0人
itbird01
HDU 2036 改革春风吹满地
题意:“ 改革春风吹满地,
不会AC没关系;
实在不行回老家,
还有一亩三分地。
谢谢!(乐队奏乐)”
话说部分学生心态极好,每天就知道游戏,这次考试如此简单的题目,也是云里雾里,而且,还竟然来这么几句打油诗。
好呀,老师的责任就是帮你解决问题,既然想种田,那就分你一块。
这块田位于浙江省温州市苍南县灵溪镇林家铺子村,多边形形状的一块地,原本是linle 的,现在就准备送给你了。不过,任何事情都没有那么简单,你必须首先告诉我这块地到底有多少面积,如果回答正确才能真正得到这块地。
发愁了吧?就是要让你知道,种地也是需要AC知识的!以后还是好好练吧...
解题思路
1.首先,我们不可能直接丘多边形的面积,而是将其分解为常见的三角形,所以这时第一个问题转换为,边数与三角形个数的关系是,由类推我们可知,一个多边形可分成的三角形个数=边数-2
2.其次,我们需要知道如何求三角形的面积,这里借助解析几何公式即可,设三点坐标,A(x1,y1),B(x2,y2),C(x3,y3),则三角形面积为 S=|x1y2+x3y1+x2y3-x1y3-x2y1-x3y2|/2
3.接下来就很简单了,我们只需迭代,去求取,以第一个点为所有三角形的一个点,然后从输入的点列表中,逆时针选择两个点,来组合为三角形,求取面积
解题遇到的问题
1.理解题意,对输入输出做分析
2.在求取面积的过程中,很有可能遇到负面积,也就是凹三角形,这时,不应该求取绝对值,因为我们求取的是整个多边形面积,所以要减去此三角形
3.为什么总是以第一个点为起点,看下图就很清晰了,如图,是一个五边形,有五个点,那只需求取图中三个三角形的面积和,即为整个多边形和
后续需要总结学习的知识点
1.三点坐标,向量求面积
##解法
import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
int n = scanner.nextInt();
if (n == 0) {
break;
}
// 首先,我们不可能直接丘多边形的面积,而是将其分解为常见的三角形,所以这时第一个问题转换为,边数与三角形个数的关系是,由类推我们可知,一个多边形可分成的三角形个数=边数-2
// 其次,我们需要知道如何求三角形的面积,这里借助解析几何公式即可,设三点坐标,A(x1,y1),B(x2,y2),C(x3,y3),则三角形面积为
// S=|x1y2+x3y1+x2y3-x1y3-x2y1-x3y2|/2
LinkedList<Point> list = new LinkedList<Point>();
DecimalFormat format = new DecimalFormat("#0.0");
double ansS = 0;
while (n > 0) {
Point point = new Point(scanner.nextDouble(),
scanner.nextDouble());
list.add(point);
n--;
}
for (int i = 0; i < list.size() - 2; i++) {
ansS += list.get(0).x * list.get(i + 1).y
- list.get(0).y * list.get(i + 1).x
+ list.get(i + 1).x * list.get(i + 2).y
- list.get(i + 1).y * list.get(i + 2).x
+ list.get(i + 2).x * list.get(0).y
- list.get(i + 2).y * list.get(0).x;
}
System.out.println(format.format(ansS / 2));
}
scanner.close();
}
public static class Point {
double x;
double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
}