首页 > 代码库 > 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;}
View Code

 

Segments---poj3304(判断直线与线段的位置关系)