欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}