题解 poj 3304

题目描述

线段和直线判交板子题

分析题目，如果存在这一条直线，那么过这条直线作垂线，一定有一条垂线穿过所有线段，否则不存在。题目转化为寻找一条直线与所有线段有交点。

直线线段判交方法：

1.先判断线段端点是否在直线上

2.如果端点不在直线上，则判断线段两端点是否分别位于直线两侧，做两次叉乘即可

考虑如何枚举直线。上述的这条垂线，如果在穿过所有线段的情况下将其平移，一定会碰到某条线段的端点；接着将其旋转一定角度，一定会碰到另一个端点。所以，只需枚举某两个端点构成的直线即可。时间复杂度O(n^3)

注意细节：

1.n=1时应输出Yes

2.两个端点相等(题目要求的范围内)时应跳过

具体实现见代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <cmath>

#define il inline

using namespace std;

struct point{

	double x, y;

};

struct segment{

	point l, r;

};

il double area(point p, point q, point s)

{

	return p.x * q.y - p.y * q.x + q.x * s.y - q.y * s.x + s.x * p.y - s.y * p.x;

}

il bool toLeft(point p, point q, point s)

{

	return area(p, q, s) > 0;

}

il bool check(segment a, segment l)

{

	if (fabs(area(l.l, l.r, a.l)) <= 1e-6 || fabs(area(l.l, l.r, a.r)) <= 1e-6)

		return 1;

	return toLeft(l.l, l.r, a.l) != toLeft(l.l, l.r, a.r);

}

int main()

{

	// ios::sync_with_stdio(false);

	// cin.tie(0);

	// cout.tie(0);

	int T, n;

	segment t;

	cin >> T;

	while (T--)

	{

		bool p = 0, ppp = 0;

		cin >> n;

		vector<segment> v;

		vector<point> v2;

		for (int i = 1; i <= n; ++i)

		{

			cin >> t.l.x >> t.l.y >> t.r.x >> t.r.y;

			v.push_back(t);

			v2.push_back(t.l);

			v2.push_back(t.r);

		}

		if (n == 1)

		{

			cout << "Yes!\n";

			continue;

		}

		for (int i = 0; i < v2.size(); ++i)

		{

			for (int j = 0; j < v2.size(); ++j)

			{

				p = 0;

				t.l = v2[i];

				t.r = v2[j];

				if (fabs(t.l.x - t.r.x) < 1e-8 && fabs(t.l.y - t.r.y) < 1e-8)

					continue;

				for (int kk = 0; kk < v.size(); ++kk)

				{

					auto k = v[kk];

					if (!check(k, t))

					{

						p = 1;

						break;

					}

				}

				if (!p)

				{

					cout << "Yes!\n";

					ppp = 1;

					break;

				}

			}

			if (ppp)

				break;

		}

		if (!ppp)

			cout << "No!\n";

	}

	return 0;

}

巴特西

题解 poj 3304

线段和直线判交板子题

最新文章

热门文章