频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 1127 Jack Straws (线段相交+并查集)
2014-09-16 11:01:47         来源:GLSilence的专栏  
收藏   我要投稿

 

Jack Straws

 

题目大意:给你一些塑料棒,散落在平面上,如果两个棒相交,那么这两个就是一堆的。假如1跟2相交,2跟3相交,1跟3不相交,那么1、2、3是一堆的,如果1跟3也相交,那么1、2、3更是一堆的了。

接下来有多个输入询问,输入两个塑料棒的编号,问这两个编号的塑料棒是不是一堆的(输入0 0时询问结束)。

 

解题思路:整体看上去是一个并查集的问题,因为只要是相交的就是一堆的,很明显的并查集。剩下的就是判断线段相交的问题了,注意线段共端点、共线都属于相交的范畴,不是个规范相交。

 

具体代码如下:

 

#include 
#include 
#include 
#include 
#define sqr(x) ((x)*(x))
#define zero(x) (((x) > 0 ? (x) : (-x)) < eps)
using namespace std;
const double eps = 1e-8;

struct Point {
    double x, y;
} ;
struct Line {
    Point a, b;
} L[20];

double xmult(Point a, Point b, Point c) {
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

///若共线,返回1;不共线,返回0。
int dot_inLine(Point p1, Point p2, Point p3){
    return zero(xmult(p1, p2, p3));
}

///判两点在线段同侧,点在线段上返回0
int same_side(Point p1, Point p2, Line l){
    return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}

///判点是否在线段上,包括端点
int dot_onLine_in(Point p, Line l){
    return zero(xmult(p, l.a, l.b)) && (l.a.x-p.x)*(l.b.x-p.x) < eps && (l.a.y-p.y)*(l.b.y-p.y) < eps;
}


///判两线段相交,包括端点和部分重合
int intersect_in(Line u, Line v){
    if (!dot_inLine(u.a, u.b, v.a)
        || !dot_inLine(u.a, u.b, v.b))
        return !same_side(u.a, u.b,v) && !same_side(v.a, v.b,u);
    return dot_onLine_in(u.a, v) || dot_onLine_in(u.b, v)
        || dot_onLine_in(v.a, u) || dot_onLine_in(v.b, u);
}

int f[100];

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void unionSet(int x, int y) {
    x = find(x);
    y = find(y);
    if(x != y) {
        f[x] = y;
    }
}

int main()
{
    int n;
    while(~scanf(%d, &n) && n) {
        for(int i = 1; i <= n; ++i) {
            f[i] = i;
        }
        for(int i = 1; i <= n; ++i) {
            scanf(%lf%lf%lf%lf, &L[i].a.x, &L[i].a.y, &L[i].b.x, &L[i].b.y);
        }
        int p, q;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(intersect_in(L[i], L[j])) {
                    unionSet(i, j);
                }
            }
        }
        while(scanf(%d%d, &p, &q) && (p||q)){
            if(find(q) == find(p)) {
                puts(CONNECTED);
            }
            else {
                puts(NOT CONNECTED);
            }
        }
    }

    return 0;
}


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 查集
上一篇:HDU 1063/POJ 1001-Exponentiation(大数类)
下一篇:HDU 1042-N!(大数类)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站