POJ 3304 Segments(计算几何)

Description:

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input:

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1 y1 x2 y2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output:

For each test case, your program must output “Yes!”, if a line with desired property exists and must output “No!” otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10^-8.

Sample Input:

3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0

Sample Output:

Yes!
Yes!
No!

题目链接

判断是否存在一条直线使所有线段映射到直线之后有交点。

若存在直线则在交点做垂线必定与所有线段相交，所以问题就转化为求这条垂线，这条垂线一定是其中某两条线段的两个端点所在直线，根据题目数据范围推算这两个端点可以直接暴力枚举找出。

AC代码:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int maxn = 1e2 + 5;
const double eps = 1e-8;

// 点
struct Point {
	double X, Y;
	void Input() {
		scanf("%lf%lf", &X, &Y);
	}
	// 坐标相减
	Point operator - (const Point &B) {
		return Point {X - B.X, Y - B.Y};
	}
	// 点乘
	double operator * (const Point &B) {
		return X * B.X + Y * B.Y;
	}
	// 叉乘
	double operator ^ (const Point &B) {
		return X * B.Y - Y * B.X;
	}
};

// 线段
struct Segment {
	// 端点S、T
	Point S, T;
	void Input() {
		S.Input();
		T.Input();
	}
};

int T;
int N;
bool Flag;
Segment segments[maxn];

bool Check(Segment X) {
	// 去除重合的点
	if (hypot(X.S.X - X.T.X, X.S.Y - X.T.Y) <= eps) {
		return false;
	}
	for (int i = 0; i < N; ++i) {
		// 判断线段X所在直线是否与所有线段都相交
		if (((X.S - segments[i].S) ^ (X.T - segments[i].S)) * ((X.S - segments[i].T) ^ (X.T - segments[i].T)) > eps) {
			return false;
		}
	}
	return true;
}

int main(int argc, char *argv[]) {
	for (int Case = 1; Case <= T; ++Case) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i) {
			segments[i].Input();
		}
		Flag = false;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				// 检验是否有两个断电所在直线可以与所有线段相交
				if (Check(Segment {segments[i].S, segments[j].S}) || Check(Segment {segments[i].S, segments[j].T}) || Check(Segment {segments[i].T, segments[j].S}) || Check(Segment {segments[i].T, segments[j].T})) {
					Flag = true;
					break;
				}
			}
			if (Flag) {
				break;
			}
		}
		if (Flag) {
			printf("Yes!\n");
		}
		else {
			printf("No!\n");
		}
	}
	return 0;
}