题干：
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 x1y1 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!
题目大意：
给出n条线段，判断是否存在有一条直线，满足所有的线段在直线上投影后至少有一个公共点。
解题报告：
原命题等价为存在一条直线穿过所有的线段（易知过公共点且垂直于所求直线的直线符合条件，设为直线a），该命题又等价于从所有线段中任选两端点形成的直线存在可以穿过所有的线段的直线（可将a平移至一条线段端点，然后绕这点旋转，使a过另一条线段端点）
这样我们只需要枚举顶点就可以了，把直线与线段的直线问题转化成了线段的端点！！
AC代码：
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const double eps = 1e-8;
int sgn(double x) {
if(fabs(x) < eps)return 0;
if(x < 0) return -1;
return 1;
}
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 s,e;
Line() {}
Line(Point s,Point e):s(s),e(e){}
};
double xmult(Point p0,Point p1,Point p2) { //p0p1 X p0p2
return (p1-p0)^(p2-p0);
}
bool Seg_inter_line(Line l1,Line l2) { //判断直线l1和线段l2是否相交
return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e)) <= 0;
}
double dist(Point a,Point b) {
return sqrt((b - a)*(b - a));
}
const int MAX = 110;
Line line[MAX];
int n;
bool ok(Line l1) {
if(sgn(dist(l1.s,l1.e)) == 0 )return 0;//如果说是个点的话。
for(int i = 1; i <= n; i++)
if(Seg_inter_line(l1,line[i]) == 0) return 0;
return 1;
}
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%d",&n);
double x1,y1,x2,y2;
for(int i = 1; i<=n; i++) {
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[i] = Line(Point(x1,y1),Point(x2,y2));
}
bool flag = 0;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n; j++)
if(ok(Line(line[i].s,line[j].s)) || ok(Line(line[i].s,line[j].e))|| ok(Line(line[i].e,line[j].s)) || ok(Line(line[i].e,line[j].e)) ) {
flag = 1;
break;
}
if(flag) puts("Yes!");
else puts("No!");
}
return 0;
} 总结：
注意牵扯异或预算的，都需要加括号，因为异或的优先级比较低，类似于if( (p^q) <= 0) 这种，必须要加括号！！（p和q都是Point类型）
京公网安备 11010502036488号