首页 > 代码库 > HDU 3492 (直线与所有线段相交) Segment
HDU 3492 (直线与所有线段相交) Segment
题意：
给出n个线段，判断是否存在一条直线使得所有线段在直线上的射影的交非空。
分析：
如果我们找到一条与所有线段相交的直线，然后做一条与该直线垂直的直线，这些线段在直线上的射影就一定包含这个垂足。
所以我们只要判断是否存在一条直线与所有的点相交即可。
如果存在这样一条直线，那么将这条直线平移或者旋转，就会被这些线段中的某两个端点“卡”住。
所以我们枚举两个端点，然后判断这些线段是否与这两个点所在的直线都相交即可。
本以为是一道很简单的计算几何，结果卡了好几天。
看了别人的题解，才发现问题所在。
http://www.cppblog.com/acronix/archive/2010/08/17/123765.html
因为有可能存在重点，所以要判断，弄了个标志变量issame，如果所有的点都是同一个点那么也应该输出Yes
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 600 + 10; 5 const double eps = 1e-8; 6 struct Point 7 { 8 double x, y; 9 Point(double x=0, double y=0):x(x), y(y) {}10 }p[maxn];11 int dcmp(double x)12 {13 if(fabs(x) < eps) return 0;14 return x < 0 ? -1 : 1;15 }16 17 Point operator - (const Point& a, const Point& b)18 { return Point(a.x-b.x, a.y-b.y); }19 20 double Cross(const Point& a, const Point& b)21 { return (a.x*b.y - a.y*b.x); }22 23 bool operator == (const Point& a, const Point& b)24 { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; }25 26 bool intersect(const Point& a, const Point& b, const Point& p1, const Point& p2)27 {28 int d1 = dcmp(Cross(b-a, p1-a));29 int d2 = dcmp(Cross(b-a, p2-a));30 if(d1 == 0 || d2 == 0) return true;31 if(d1 * d2 < 0) return true;32 return false;33 }34 35 int main(void)36 {37 //freopen("3492in.txt", "r", stdin);38 int T;39 scanf("%d", &T);40 while(T--)41 {42 int n;43 scanf("%d", &n);44 for(int i = 0; i < 2*n-1; i += 2)45 scanf("%lf%lf%lf%lf", &p[i].x, &p[i].y, &p[i+1].x, &p[i+1].y);46 47 bool exist = false;48 bool issame = true;49 for(int i = 0; i < 2*n-1 && !exist; ++i)50 {51 for(int j = i+1; j < 2*n && !exist; ++j)52 {53 if(p[i] == p[j]) continue;54 issame = false;55 int k;56 for(k = 0; k < 2*n; k += 2)57 if(!intersect(p[i], p[j], p[k], p[k+1])) break;58 if(k == 2 * n)59 exist = true;60 }61 }62 63 if(exist || issame) puts("Yes");64 else puts("No");65 }66 67 return 0;68 }
HDU 3492 (直线与所有线段相交) Segment
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。