首页 > 代码库 > Segments---poj3304(判断直线与线段的位置关系)
Segments---poj3304(判断直线与线段的位置关系)
题目链接:http://poj.org/problem?id=3304
题意:给你n个线段,求是否有一条直线与所有的线段都相交,有Yes,没有No;
枚举所有的顶点作为直线的两点,然后判断这条直线是否和所有的线段相交即可;注意不能找两个相同的点作为直线上的两点;
#include<iostream>#include<algorithm>#include<math.h>#include<string.h>#include<stdio.h>#include<queue>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef long long LL;const int N = 5050;const int INF = 0x3f3f3f3f;const double eps = 1e-8;struct point{ double x, y; point(double x=0, double y=0) : x(x), y(y) {} friend point operator -(point p1, point p2) { return point(p1.x-p2.x, p1.y-p2.y); } friend int operator ^(point p1, point p2) { double k = p1.x*p2.y - p1.y*p2.x; if(k > eps) return 1; if(fabs(k) < eps) return 0; return -1; } friend int operator ==(point p1, point p2) { return (p1.x == p2.x && p1.y == p2.y); }}p[N];struct line{ point s, e; line(point s=0, point e=0) : s(s), e(e) {}}Line[N];int Judge(line l, line L[], int n){ for(int i=1; i<=n; i++) { int k = abs( ((l.s-l.e)^(L[i].s-l.e)) + ((l.s-l.e)^(L[i].e-l.e)) ); ///判断直线l是否与线段L[i]相交; if(k == 2) return 0;///不相交; } return 1;}int main(){ int T, n; scanf("%d", &T); while(T--) { met(p, 0); met(Line, 0); int k = 0; scanf("%d", &n); for(int i=1; i<=n; i++) { double x1, x2, y1, y2; scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); p[k++] = point(x1, y1); p[k++] = point(x2, y2); Line[i] = line(p[k-2], p[k-1]); } int flag = 0; for(int i=0; i<k && !flag; i++) { for(int j=0; j<i && !flag; j++) { if(p[i] == p[j]) continue; flag = Judge(line(p[i], p[j]), Line, n); } } if(flag) puts("Yes!"); else puts("No!"); } return 0;}
Segments---poj3304(判断直线与线段的位置关系)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。