系统之家论坛dadawl,林丹谢杏芳婚纱照,卫星发射失败
给定n条线段,确定是否存在一条直线,使得这n条线段在这条直线上的投影具有公共点。
n<=100
非常妙的一个题。
我们考虑如果所有线段的投影有重合部分,那么我们可以在重合部分上做一条垂线经过所有点
同时我们平移一下这个直线,一定可以与某个点重合。
然后考虑旋转一下,一定可以交于某个最近的点(最近的定义是旋转最小的角度与之相交)
那么我们就搞出了一个\(n^3\)的做法:暴力枚举两个点构成的直线,判断是否与所有点相交
判断直线与线段相交可以用叉积
如果线段上的两点与直线的端点连线的叉积均同号的话,说明线段在直线的两侧。
否则说明相交
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn = 1001; const double eps = 1e-10; int n; struct point { double x, y; point operator - (const point &rhs) const { return {x - rhs.x, y - rhs.y}; } double operator ^ (const point &rhs) const { return x * rhs.y - y * rhs.x; } bool operator == (const point &rhs) const { return (x - rhs.x) < eps && (y -rhs.y) < eps; } }; struct l { point a, b; }; point line[maxn][2]; int dcmp(double x) { if(fabs(x) < eps) return 0; return x > 0 ? 1 : -1; } bool judge(l l1, l l2) { point tmp = l1.a - l1.b; bool flag = dcmp(dcmp(tmp ^ (l2.b - l1.b)) * dcmp(tmp ^ (l2.a - l1.b))) != 1; return flag; } bool check(point a, point b) { if(a == b) return 0; for(int i = 1; i <= n; i++) if(!judge({a, b}, {line[i][0], line[i][1]})) return 0; return 1; } void solve() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lf %lf %lf %lf", &line[i][0].x, &line[i][0].y, &line[i][1].x, &line[i][1].y); for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) for(int k = 1; k <= n; k++) for(int l = 0; l < 2; l++) if(check(line[i][j], line[k][l])) {puts("yes!"); return ;} puts("no!"); } int main() { int t; scanf("%d", &t); for(; t; t--, solve()); }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论