判断直线与线段是否相交 + 加入误差故需要判断重点 poj 3304 Segments

题目来源：http://poj.org/problem?id=3304

分析：

题目大意：给出n条线段两个端点的坐标，问所有线段投影到一条直线上，如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。
解题思路：如果存在这样的直线，过投影相交点（或投影相交区域中的点）作直线的垂线，该垂线（也是直线）必定与每条线段相交，问题转化为问是否存在一条直线和所有线段相交。
若存在一条直线与所有线段相交，此时该直线必定经过这些线段的某两个端点，所以枚举任意两个端点即可。
这里要注意的地方就是，题目说如果两个点的距离小于1e-8就等价于一点（即重点），所以要考虑重点。

判断直线与线段是否相交函数：

const double EPS = 1e-12 ;
double add(double a, double b){
    return (fabs(a + b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b);
}
struct Point{
    double x, y;
    Point(){}
    Point(double x, double y):x(x),y(y){}
    double operator ^(Point a){
        return add(x * a.y ,- y * a.x );
    }
    Point operator - (Point a){
        return Point(add(x ,- a.x) , add(y ,- a.y)) ;
    }
    void read(){
        scanf("%lf%lf" , &x ,&y) ;
    }
};
struct Line{
    Point st, ed;
    Line(){}
    Line(Point st, Point ed):st(st),ed(ed){}
    bool intersection(Line l){  // 当前直线与线段 L 相交返回 1， 否则 返回0
       double d1  = (ed -st)^(l.st - st) , d2 = (ed - st)^(l.ed - st) ;
       return d1 * d2 <= 0 ;
    }
};

代码如下：

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include<map>
using namespace std;
typedef long long ll;
const int N =300;
const double PI = 3.1415927;
const double EPS=1e-8;
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){} // 构造函数，方便代码编写
    Point(const Point & p):x(p.x),y(p.y){}
    Point operator +(Point p){
        return Point(x+p.x,y+p.y);
    }
    Point operator-(Point p){
        return Point(x-p.x,y-p.y);
    }
    Point operator*(double d){
        return Point(x*d,y*d);
    }
    double operator*(Point p){  // 内积 点乘
        return x*p.x+ y*p.y;
    }
    double operator^(Point p){//  外积 叉乘
        return x*p.y-y*p.x;
    }
    friend ostream& operator<<(ostream& os,const Point& p ){
        os<<p.x<<" "<<p.y<<endl;
        return os;
    }
    friend istream& operator>>(istream& is, Point& p) {// Point 不能是常量，是变量
        is>>p.x>>p.y;
        return is;
    }
    double dist(Point p){
        return sqrt( (x-p.x)*(x-p.x)+ (y-p.y)*(y-p.y) );
    }
};
Point List[N]; // List[0]~List[n-1] 存的是线段的起点， List[n]~List[2*n-1] 存的是线段的终点

int n;
// 判断直线p1p2与所有线段q1q2是否相交
bool intersection(Point p1,Point p2)
{
    if(p1.dist(p2)<EPS ) return 0;  // 判断重点
    Point q1,q2;
    for(int i=0;i<n;i++)
    {
        q1=List[i];
        q2=List[n+i];
        double d1=( (p2-p1)^(q1-p1) );
        double d2=( (p2-p1)^(q2-p1) );
        if(d1*d2 > EPS) return 0;    // 一旦有一条线段不相交，则返回0
    }
    return 1;
}
void solve()
{
    for(int i=0;i<n*2;i++)   // 枚举所有端点中任取2个端点确定的一条直线
    {
        for(int j=i+1;j<n*2;j++)
        {
            if(intersection(List[i],List[j]) )
            {
                puts("Yes!");
                return ;
            }
        }
    }
    puts("No!");
}
int main() {

    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>List[i]>>List[n+i];
        if(n==1) 
        {
            puts("Yes!");
            continue;
        }
        solve();
    }
    return 0;
}

判断直线与线段 是否相交 + 加入误差 故需要判断重点 poj 3304 Segments

相关推荐

判断直线与线段是否相交 + 加入误差故需要判断重点 poj 3304 Segments