暑假集训#2 div1 J 四点直角 J - Space Invader 四点共面+跨立实验
2024-09-02 08:12:48
题意:给你四个点,判断能否先依次通过A,B两点,然后再在某个地方只进行一次直角转弯再一次经过C,D两点;
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const double eps=1e-12;
struct Point{
double x,y,z;
void read(){
scanf("%lf %lf %lf",&x,&y,&z);
};
}; int dcmp(double a)
{
if(fabs(a)<eps) return 0;
return a>0?1:-1;
} double Dot(Point a,Point b)
{
return a.x*b.x+a.y*b.y+a.z*b.z;
} Point cross(Point a,Point b)
{
return Point{a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};
}
Point operator-(Point a,Point b)
{
return Point{a.x-b.x,a.y-b.y,a.z-b.z};
}
double dis(Point a,Point 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));
}
int main()
{
Point a,b,c,d;
a.read();b.read();c.read();d.read();
Point ab=b-a,cd=d-c,ca=a-c,cb=b-c,ad=d-a,ac=c-a;
if(Dot(ab,cd)!=0||Dot(ab,cross(ad,cd))!=0) {printf("Invalid\n");return 0;}
double x1=Dot(cross(cd,ca),cross(cd,cb)),
x2=Dot(cross(ab,ac),cross(ab,ad));
if(dcmp(x1)>=0&&dcmp(x2)>=0)
{
if(dis(b,c)>=dis(a,c)||dis(c,b)>=dis(d,b)) printf("Invalid\n");
else printf("Valid\n");
}
else printf("Invalid\n");
return 0;
}
分析:这道题涉及到了几个知识点:
1.判断四点是否共面
if(Dot(ab,cross(ad,cd))!=0)
代码如上,假设平面有A,B,C,D四点,那么先求出a,c,d三点确定的平面的一个法向量方向的向量,
然后再判断向量ab是否垂直该向量。
2.因为即使ab与cd垂直且共面,也不一定就满足条件,因为可能是ab与cd规范相交(不在端点处
相交),那么这个时候就需要进行跨立实验判断是否两条线段都只在对方的同一侧了
3.即使二满足了,也不一定是正确的,因为题目要求的是一次经过A,B,C,D四点,那么还要判断下
四个点的相对位置关系,不过因为已经确定了垂直关系,那么这个时候只需要比较下点之间的距离
就可以确定了
J - Space Invader
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. For example, Eugene creates computer games in the evenings. His current game has a very simple game play — user controls a spaceship flying in 3D space. To test the mechanics of the movement of his spaceship Eugene wants to solve the following problem: can his spaceship, moving in a straight line, fly through the points A and B, then make a turn at 90°, and then fly through the points C and D, continuing to move in a straight line. The points A, B, C, D should be visited by the spaceship in just that order, the turning point may coincide with the point B or the point C. The spaceship should be considered as a material point.
Input
There are four lines, each containing integers xi, yi, zi that are the coordinates of the points A, B, C, D respectively(−10 6 ≤ xi, yi, zi ≤ 10 6) . All points are pairwise different.
Output
If the spaceship can fly through the data points, output “Valid”, otherwise output “Invalid”.
Sample Input
input | output |
---|---|
-2 0 0 |
Valid |
最新文章
- PHP js使用ajax异步处理方式请求PHP,解决数组中文乱码
- Java系列:JVM指令详解(上)(zz)
- Linux man命令数字含义
- iOS开发——测试篇&;breakpoints、lldb 和 chisel 的详解
- haproxy path_end不能忽略
- ER 和 数据库关系模式
- uva 12003 Array Transformer (大规模阵列)
- img onerror事件
- java 区分error和exception
- Alamofire源码解读系列(六)之Task代理(TaskDelegate)
- 带你玩转 jQuery
- This version of the rendering library is more recent than your version of IntelliJ IDEA.
- 瑞芯微发布最新旗舰应用处理器-RK3588
- [物理学与PDEs]第1章习题15 媒介中电磁场的电磁动量密度向量与电磁动量流密度张量
- sin n次方 x 的降幂公式
- mysql_config_editor usage
- playframework链接MySQL数据库的问题
- 【JVM.8】类加载及执行子系统的案例与实战
- 关于形如--error LNK2005: xxx 已经在 msvcrtd.lib ( MSVCR90D.dll ) 中定义--的问题分析解决
- spring boot启动报内存溢出的问题