一条线段关于特定直线的投影是指：分别从这条线段的两个端点对特定直线作垂线，两垂足之间的距离就是其投影。
如果有一条直线穿过了所有已知线段，那么作任意一条垂直于该直线的直线L，则所有线段在L上的投影必定有交点。因此这题就是求是否存在一条直线穿过所有已知线段。那么问题是怎么枚举这条线段呢？
可以注意到，若在由平面上的任两点确定出的所有直线中，不存在符合要求的直线那么在平面中肯定不存在符合要求的直线。因此，我们只需要用题目所给的2n个点，两点确定一条直线，验证这条直线是否穿过所有线段即可。
验证一条直线是否穿过一条线段比验证两线段相交简单多了，只需要考虑线段是否跨过线段即可。利用叉乘即可解决。
注意数据中存在在精度之内的相同点，组成直线的时候要注意此时不能取。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cmath>
#include <iostream>
using namespace std;
int T, n;
struct Point
{
double x, y;
} p[200];
inline double sqr(const double& a) { return a*a; }
inline double xmul(const Point& A, const Point& B, const Point& C, const Point& D)
{
const double x1 = B.x-A.x, y1 = B.y-A.y;
const double x2 = D.x-C.x, y2 = D.y-C.y;
return x1*y2-y1*x2;
}
int main()
{
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> p[i].x >> p[i].y >> p[i+n].x >> p[i+n].y;
bool exist = false;
for (int i = 0; i < 2*n && !exist; ++i)
for (int j = i+1; j < 2*n && !exist; ++j)
{
if (!(sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))>1e-8))
continue;
exist = true;
for (int k = 0; k < n && exist; ++k)
exist = !(xmul(p[i], p[k], p[i], p[j])*xmul(p[i], p[k+n], p[i], p[j]) > 1e-8);
}
cout << (exist ? "Yes!" : "No!") << endl;
}
}
|
