Intersecting Lines POJ 1269 (几何 叉积 直线交点)
程序员文章站
2022-03-30 08:39:29
...
题目地址:http://poj.org/problem?id=1269
思路:先用叉积判断两条直线是否(共线、平行)或(相交);是共线、平行的情况下,再用叉积判断是共线还是平行;相交的情况下,用直线的性质求交点。
如何由两点坐标确定一条直线的ax+by+c=0表达式
比如已知两坐标:
(x1,y1),(x2,y2);
对于表达式ax+by+c=0;
a=?,b=?,c=?;
y=kx+m,
y1=kx1+m
y2=kx2+m,
k=(y2-y1)/(x2-x1)
m=y1-(y2-y1)x1/(x2-x1)
y=(y2-y1)/(x2-x1)x+(y1(x2-x1)-x1(y2-y1))/(x2-x1)
(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0,
a=y1-y2,
b=x2-x1,
c=x1y2-x2y1
假设有二元一次方程组
a1x+b1y+c1=0;
a2x+b2y+c2=0
那么
x=(c1* b2-c2* b1)/(a2* b1-a1* b2);
y=(a2* c1-a1* c2)/(a1* b2-a2* b1);
因为此处两直线不会平行,所以分母不会为0。
部分思路来源于:https://blog.csdn.net/dreamvyps/article/details/6162690
在Virtual Judge上写的,G++要用%.2f C++用 %.2lf 这个原因wrong了好几发 哭哭
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define eps 1e-8
using namespace std;
bool chaji( int x1,int y1,int x2,int y2)
{
int ans=x1*y2-x2*y1;
if(ans==0)
return true;
return false;
}
int main()
{
int n;
int x1,x2,x3,x4,y1,y2,y3,y4;
int x5,x6,y5,y6;
scanf("%d",&n);
printf("INTERSECTING LINES OUTPUT\n");
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
x5=x2-x1; y5=y2-y1;
x6=x4-x3; y6=y4-y3;
if(chaji(x5,y5,x6,y6))
{
x5=x3-x1; y5=y3-y1;
x6=x4-x1; y6=y4-y1;
if(chaji(x5,y5,x6,y6))
printf("LINE\n");
else
printf("NONE\n");
}
else
{
double a1=double(y1-y2);
double a2=double(y3-y4);
double b1=double(x2-x1);
double b2=double(x4-x3);
double c1=double(x1*y2-x2*y1);
double c2=double(x3*y4-x4*y3);
double x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
double y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
printf("POINT %.2lf %.2lf\n",x,y);
/*
x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
y=(a2*c1-a1*c2)/(a1*b2-a2*b1);*/
}
}
printf("END OF OUTPUT\n");
return 0;
}
上一篇: poj3714(平面最近点对)
下一篇: poj 3714 - 平面最近点对
推荐阅读
-
Intersecting Lines POJ - 1269(判断直线相交(交点)、平行、重合)
-
[POJ1269]Intersecting Lines(计算几何-叉积)
-
poj 1269 Intersecting Lines 【直线相交】
-
POJ 1269 Intersecting Lines (两直线位置关系+求交点)
-
POJ 1269 Intersecting Lines (叉积 -- 判断直线位置)
-
POJ 1269 Intersecting Lines (两直线位置关系)
-
【POJ - 1269 】Intersecting Lines (计算几何,直线间的位置关系)
-
简单几何(直线位置) POJ 1269 Intersecting Lines
-
POJ 1269 Intersecting Lines(计算几何) (两线段位置)
-
Intersecting Lines POJ - 1269(计算几何判断直线位置关系+求直线交点)