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

●POJ 1269 Intersecting Lines

程序员文章站 2022-04-02 16:59:15
...

题链:

http://poj.org/problem?id=1269

题解:

计算几何,直线交点

模板题,试了一下直线的向量参数方程求交点的方法。

(方法详见《算法竞赛入门经典——训练指南》P257)

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct Point{
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}
double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}
int N;
bool Point_on_Line(Point P,Vector v,Point Q){
	return ((Q-P)^v)==0;
}
Point Line_Intersection(Point P,Vector v,Point Q,Vector w){
	static Vector u; static double t1;
	u=P-Q;
	t1=(w^u)/(v^w);
	return P+v*t1;
}
int main(){
	Vector v,w;
	Point P,_P,Q,_Q,D;
	scanf("%d",&N);
	printf("INTERSECTING LINES OUTPUT\n");
	while(N--){
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&P.x,&P.y,&_P.x,&_P.y,&Q.x,&Q.y,&_Q.x,&_Q.y);
		v=_P-P;	w=_Q-Q;
		if((v^w)==0){//向量共线
			if(Point_on_Line(P,v,Q)) printf("LINE");
			else printf("NONE");
		}
		else{
			D=Line_Intersection(P,v,Q,w);
			printf("POINT %.2lf %.2lf",D.x,D.y);
		}
		printf("\n");
	}
	printf("END OF OUTPUT\n");
	return 0;
}