POJ-3304-Segments(直线与线段相交)

题目链接

POJ-3304

题意

给出n条线段,问你是否存在这样一条直, 使得所有线段在直线上的投影均有公共部分

思路

画图易得,投影直线上有公共点的话就是说这条直线存在一个垂线经过所有线段
只要枚举这些线段端点所确定的直线 是否存在一条与所有线段均相交即可

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 10000+10;
const int mod = 1e9+7;
const double eps = 1e-10;
int n , m;
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y)
{
x = _x;y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x,y - b.y);
}
double operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
double operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
};
struct Line
{
Point a,b;
Line(){}
Line(Point aa,Point bb):a(aa),b(bb){}
};
int sgn(double x)
{
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
bool check(Line l1 , Line l2)
{
return sgn((l2.a-l1.b)^(l1.a-l1.b))*sgn((l2.b-l1.b)^(l1.a-l1.b)) <= 0;
}
bool dis(Point a ,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)) <= eps;
}
vector<Point> p;
vector<Line> l;
bool solve()
{
for(int i = 0 ; i < p.size() ; i ++){
for(int j = i + 1 ; j < p.size() ; j ++){
if(dis(p[i],p[j]))continue;
Line L = Line(p[i] , p[j]);
bool flag = true;
for(int k = 0 ; k < l.size() ; k ++){
if(!check(L , l[k]))flag = false;
}
if(flag == true)return true;
}
}
return false;
}
int main(int argc, char const *argv[])
{
int T;
cin >> T;
while(T--){
p.clear();
l.clear();
int n;
cin >> n;
for(int i = 0 ; i < n ; i ++){
double x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
p.push_back(Point(x1,y1));
p.push_back(Point(x2,y2));
l.push_back(Line(Point(x1,y1) , Point(x2,y2)));
}
if(solve())cout << "Yes!" << endl;
else cout << "No!" << endl;
}
return 0;
}