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

判断是否所有直线交于一点

程序员文章站 2022-03-13 12:04:18
...

t,样例个数

n,直线条数

p,交点

代码:

//此程序可以判断是否所有直线交于一点 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<vector>
#include<cmath> 
#include<map>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const double esp = 1e-7;
const int ff = 0x3f3f3f3f;

struct node
{
	double x;
	double y;
	node(double x = 0,double y = 0):x(x),y(y){}
};

struct line 
{
	node a,b;
} l[520];

int n,flag;

int fork(node p0,node p1,node p2)
{
	return (p0.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p0.y-p1.y);//计算向量叉乘 
}


node calculate(double k1,double b1,double k2,double b2)
{
	node p;
	p.x = (b2-b1)/(k1-k2);
	p.y = p.x*k1+b1;
	return p;
}

node find()//返回两条相交直线的交点 
{
	for(int i = 1;i< n;i++)
	{
		double k1 = (l[i].a.y - l[i].b.y)/(l[i].a.x - l[i].b.x);
		double b1 = l[i].a.y - l[i].a.x*k1;
		int tmp1 = 0,tmp2 = 0;
		if(fabs(l[i].a.x - l[i].b.x)< esp)
			tmp1 = 1;
		for(int j = i+1;j<= n;j++)
		{
			double k2 = (l[j].a.y - l[j].b.y)/(l[j].a.x - l[j].b.x);
			double b2 = l[j].a.y - l[j].a.x*k2;
			if(fabs(l[j].a.x - l[j].b.x)< esp)
				tmp2 = 1;
				
			if(tmp1&&tmp2||(fabs(k1-k2)< esp&&fabs(b1-b2)< esp))
				continue;
			
			if(tmp1)
				return node(l[i].a.x,l[j].a.x*k2+b2);
			else if(tmp2)
				return node(l[j].a.x,l[i].a.x*k1+b1);
				
			return calculate(k1,b1,k2,b2);
		}
	}
	return node(l[1].a.x,l[1].a.y);
}

void init()
{
	mem(l,0);
	flag = 0;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		init();
		scanf("%d",&n);
		for(int i = 1;i<= n;i++)
			scanf("%lf %lf %lf %lf",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);
		
		node p = find();
		
		for(int i = 1;i<= n;i++)//判断是否此点在所有直线上 
			if(fork(p,l[i].a,l[i].b)!= 0)
				flag = 1;
		
		if(flag)
			cout<<"No!"<<endl;
		else
		{
			cout<<"Yes!"<<endl;
			cout<<p.x<<' '<<p.y<<endl;
		}
	}
	return 0;
}

相关标签: 直线之间的关系