hihoCoder 1040 矩阵判断 最详细的解题报告
2024-10-09 06:26:47
题目来源:矩阵判断
解题思路:
1、判断矩阵的4个点是否相连,一共输入8个点,只要判断是否4个点是否都经过2遍;
2、判断矩阵中任意一条边与其他边之间要么平行,要么垂直。设A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4),则线段AB的向量为A’(x2-x1,y2-y1),线段CD的向量C'(x4-x3,y4-y3),另x2-x1=a1,y2-y1=a2,x4-x3=c1,y4-y3=c2,判断A’是否平行C'的方法是a1*c2-a2*c1=0;判断A’是否垂直C'的方法是a1*c1+a2*c2=0.
具体算法(java版,可以直接AC)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner; public class Main { public static boolean isCycled(List<Line> list) {
List<Point> temp = new ArrayList<Point>();
for (Line line : list) {
if (line.getDistance() == 0)// 保证面积大于0
return false;
if (temp.contains(line.start)) {
temp.remove(line.start);
} else {
temp.add(line.start);
}
if (temp.contains(line.end)) {
temp.remove(line.end);
} else {
temp.add(line.end);
}
}
return temp.size() == 0;
} public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Line> list = new ArrayList<Line>();
for (int i = 0; i < n; i++) {
list.clear();
for (int j = 0; j < 4; j++) {
list.add(new Line(scanner.nextInt(), scanner.nextInt(), scanner
.nextInt(), scanner.nextInt()));
}
boolean ans = true;
if (isCycled(list)) {
for (int j = 0; j < 4; j++) {
for (int k = j + 1; k < 4; k++) {
if (!list.get(j).isVerticalOrParallel(list.get(k))) {
ans = false;
break;
}
}
if (!ans)
break;
}
} else {
ans = false;
}
if (ans) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
} } class Point {
public int x;
public int y; public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Object o) {
if (this == o)
return true;
if (o instanceof Point) {
Point p = (Point) o;
return this.x == p.x && this.y == p.y;
}
return false;
} public int hashCode() {
return this.x * 10 + this.y;
}
} class Line {
public Point start;
public Point end; public Line(int x1, int y1, int x2, int y2) {
this.start = new Point(x1, y1);
this.end = new Point(x2, y2);
} private Point getVector() {
return new Point(this.end.x - this.start.x, this.end.y - this.start.y);
} private boolean isVertical(Line line) {
Point p1 = this.getVector();
Point p2 = line.getVector();
return p1.x * p2.x + p1.y * p2.y == 0;
} private boolean isParallel(Line line) {
Point p1 = this.getVector();
Point p2 = line.getVector();
return p1.x * p2.y - p1.y * p2.x == 0;
} public int getDistance() {
return (int) ((this.start.x - this.end.x) * (this.start.x - this.end.x) + (this.start.y - this.end.y)
* (this.start.y - this.end.y));
} public boolean isVerticalOrParallel(Line line) {
return this.isParallel(line) || this.isVertical(line);
}
}
最新文章
- 获取FIle路径下所有文件的地址和名称
- Script 语言的简单练习题 乘法口诀
- 一、Owin Identity的使用
- 关于sql server远程访问Oracle数据库 OpenQuery查询返回多条数据的问题
- platform
- python入门第一天作业。讲师写的代码。
- Java 中 MongoDB 使用指南
- zabbix报警把特定的应用集发送给developer
- openssl编译(VC6.0)
- VJGUI消息设计-兼谈MFC、QT和信号/槽机制
- 关于this指针理解
- 关于Apache,Mysql,PHP之间的关系
- JavaScript一看就懂(1)作用域
- Centos 7.6搭建Tomcat 环境,发布Java项目
- vSphere ESXi 重新安装后的虚拟机恢复(转载)
- char和varchar、浮点数和定点数
- unwind
- 007.FTP虚拟用户访问
- IDEA导入项目jar包红线, cannot resolve symbol xxxx问题
- Javascript开发者 常用知识
热门文章
- mysql explain的extra
- [问题解决]Windows下python中pydoc命令提示“&#39;pydoc&#39; 不是内部或外部命令,也不是可运行的程序 或批处理文件。”
- PHP丨PHP基础知识之条件语SWITCH判断「理论篇」
- java之FTP上传下载
- Redis:rdb和aof
- 【秒懂Java】【第1章_初识Java】01_编程语言
- 深入理解RocketMQ(九)---实战(控制台搭建)
- xshell界面变成半透明的怎么办?
- Nginx详细介绍
- Material Component--mdcChipSet使用