题目链接
题意
给定(n)条线段，问是否存在一条直线，使得这(n)条线段在这条直线上的投影至少有一个交点。
思路
即问是否存在一条直线与这(n)条线段都有公共点。
充分性：若存在这样一条直线，则垂直于该直线的任一条直线即可作为题中的投影直线。
因此，可以枚举两个端点得到一条直线，判断其他所有线段是否与该直线有公共点。
注意点
-
枚举的两个端点可以是同一条直线的两个端点。
-
注意判断枚举的两个端点重合的情况。
-
精度问题。
Code
/*
写了两个版本
第一个版本全裸，跑了32ms
第二个版本参考kuangbin大神的进行了封装，看起来赏心悦目~跑了94ms
*/
Ver.1
#include <cstdio>
#include <cmath>
#define maxn 110
#define eps 1e-8
using namespace std;
int n;
typedef long long LL;
struct Seg {
double x1, y1, x2, y2;
}a[maxn];
double vec(double x1, double y1, double x2, double y2, double x0, double y0) {
return (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0);
}
bool sep(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
double v1 = vec(x1, y1, x2, y2, x3, y3),
v2 = vec(x1, y1, x2, y2, x4, y4);
if (fabs(v1) < eps || fabs(v2) < eps) return true;
return v1 * v2 < 0;
}
bool check(double x1, double y1, double x2, double y2) {
if (fabs(sqrt(pow(x1-x2,2)+pow(y1-y2,2))) < eps) return false;
for (int i = 0; i < n; ++i) {
if (!sep(x1, y1, x2, y2, a[i].x1, a[i].y1, a[i].x2, a[i].y2)) return false;
}
return true;
}
void work() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf%lf%lf%lf", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
bool flag = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (check(a[i].x1, a[i].y1, a[j].x1, a[j].y1) || check(a[i].x1, a[i].y1, a[j].x2, a[j].y2)
|| check(a[i].x2, a[i].y2, a[j].x1, a[j].y1) || check(a[i].x2, a[i].y2, a[j].x2, a[j].y2)) {
flag = true;
break;
}
}
if (flag) break;
}
if (flag) printf("Yes!
");
else printf("No!
");
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}
Ver.2
#include <cstdio>
#include <cmath>
#define maxn 110
#define eps 1e-8
using namespace std;
int n;
typedef long long LL;
struct Point {
double x, y;
Point(double _x=0, double _y=0) : x(_x), y(_y) {}
double operator * (const Point& b) const {
return x * b.x + y * b.y;
}
double operator ^ (const Point& b) const {
return x * b.y - y * b.x;
}
Point operator - (const Point& b) const {
return Point(x-b.x, y-b.y);
}
};
struct Seg {
Point s, t;
Seg() {}
Seg(Point _s, Point _t) : s(_s), t(_t) {}
}a[maxn];
int sgn(double x) {
if (fabs(x) < eps) return 0;
if (x > 0) return 1;
else return -1;
}
double xmult(Point s, Point t, Point p) {
return (s-p) ^ (t-p);
}
bool Seg_inter_line(Point s0, Point t0, Point s, Point t) {
double v1 = xmult(s0, t0, s), v2 = xmult(s0, t0, t);
return sgn(v1) * sgn(v2) <= 0;
}
bool check(Point s, Point t) {
if (!sgn(sqrt((t-s)*(t-s)))) return false;
for (int i = 0; i < n; ++i) {
if (!Seg_inter_line(s, t, a[i].s, a[i].t)) return false;
}
return true;
}
void work() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf%lf%lf%lf", &a[i].s.x, &a[i].s.y, &a[i].t.x, &a[i].t.y);
bool flag = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (check(a[i].s, a[j].s) || check(a[i].s, a[j].t)
|| check(a[i].t, a[j].s) || check(a[i].t, a[j].t)) {
flag = true;
break;
}
}
if (flag) break;
}
if (flag) printf("Yes!
");
else printf("No!
");
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}