Programming 版 (精华区)

发信人: JJason (总统~~), 信区: Programming
标  题: [合集]不好意思。又一个问题！！！！！
发信站: 哈工大紫丁香 (2003年03月20日16:55:22 星期四), 站内信件


────────────────────────────────────────
 zealous (zealous)                    于 Fri Jan  3 16:52:47 2003) 说道:



如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成的一个闭
合图形？？？？


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
＝＝＝

怎么办？？？？？？？



高手求命！！！！！！！！！！！

────────────────────────────────────────
 ggyy (胖子·理想情感在心中沉淀，梦在飞扬)  于 2003年01月03日16:56:37 星期五 说道:

    要构成一个闭合的图形，图的每个端点应该有2个不同线段的1个端点，
可以检查线段端点的坐标
【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成的一个闭
: 合图形？？？？
: 
: 
: ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
: ＝＝＝
: 
: 怎么办？？？？？？？
: 

────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日16:58:15 星期五 说道:

好像不是这样的
还需要检查线段间的交点
【 在 ggyy (胖子·理想情感在心中沉淀，梦在飞扬) 的大作中提到: 】
:     要构成一个闭合的图形，图的每个端点应该有2个不同线段的1个端点，
: 可以检查线段端点的坐标
: 【 在 zealous (zealous) 的大作中提到: 】
: : 如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成的一个闭
: : 合图形？？？？

────────────────────────────────────────
 Pomegranate (石榴哥-=|863-05|=-)     于 2003年01月03日16:58:28 星期五 说道:

需要搜一下，如果这东西不重要的话，建议你别做了
【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成的一个闭
: 合图形？？？？
: 
: 
: ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
: ＝＝＝
: 
: 怎么办？？？？？？？
: 

────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日16:59:58 星期五 说道:

nod!
复杂量很大呀！
需要参考计算几何的相关资料，而且写代码也比较繁琐
【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: 需要搜一下，如果这东西不重要的话，建议你别做了
: 【 在 zealous (zealous) 的大作中提到: 】
: : 如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成的一个闭
: : 合图形？？？？
: : ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
: : ＝＝＝

────────────────────────────────────────
 ggyy (胖子·理想情感在心中沉淀，梦在飞扬)  于 2003年01月03日17:00:06 星期五 说道:

    对呀，忘了相交的情况了
    要是线段有重合的算不算一个闭合的图形？
【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 好像不是这样的
: 还需要检查线段间的交点
: 【 在 ggyy (胖子·理想情感在心中沉淀，梦在飞扬) 的大作中提到: 】
: :     要构成一个闭合的图形，图的每个端点应该有2个不同线段的1个端点，
: : 可以检查线段端点的坐标

────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日17:00:54 星期五 说道:

这个情况就需要剔除掉，可以当成一条线段处理
【 在 ggyy (胖子·理想情感在心中沉淀，梦在飞扬) 的大作中提到: 】
:     对呀，忘了相交的情况了
:     要是线段有重合的算不算一个闭合的图形？
: 【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: : 好像不是这样的
: : 还需要检查线段间的交点

────────────────────────────────────────
 zealous (zealous)                    于 Fri Jan  3 17:01:17 2003) 说道:



各位学过数据结构吗？好像里边的图论可以解决这个问题。

可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？


yes !!!???????

【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: 需要搜一下，如果这东西不重要的话，建议你别做了
: 【 在 zealous (zealous) 的大作中提到: 】
: : 
: : 
: : 如果给定了一些线段的2个端点（n个线段），如何求出是否存在由这些线段构成?..
: : 合图形？？？？
: : 
: : 
: : ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝?..
: : ＝＝＝
: : 
: : 怎么办？？？？？？？
: : 



────────────────────────────────────────
 zealous (zealous)                    于 Fri Jan  3 17:02:10 2003) 说道:



agree !!!!!!!!!!!

【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 这个情况就需要剔除掉，可以当成一条线段处理
: 【 在 ggyy (胖子·理想情感在心中沉淀，梦在飞扬) 的大作中提到: 】
: :     对呀，忘了相交的情况了
: :     要是线段有重合的算不算一个闭合的图形？
: : 【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: : : 好像不是这样的
: : : 还需要检查线段间的交点



────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日17:03:35 星期五 说道:

这个不属于图论，属于计算几何
【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: 
: 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
: 
: 
: yes !!!???????
: 
: 【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: : 需要搜一下，如果这东西不重要的话，建议你别做了

────────────────────────────────────────
 zealous (zealous)                    于 Fri Jan  3 17:04:38 2003) 说道:



是否可以搞定？？？？？

有没有相关书籍？！？？
最好直接给出源代码！！！

呵呵，太着急了！！！

【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 这个不属于图论，属于计算几何
: 【 在 zealous (zealous) 的大作中提到: 】
: : 
: : 
: : 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: : 
: : 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
: : 
: : 
: : yes !!!???????
: : 
: : 【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: : : 需要搜一下，如果这东西不重要的话，建议你别做了



────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日17:08:12 星期五 说道:

我搞不定这个东西，以前做过一部分，后来由于难度太大，放弃了
找找计算几何相关的书籍就行了
【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 是否可以搞定？？？？？
: 
: 有没有相关书籍？！？？
: 最好直接给出源代码！！！
: 
: 呵呵，太着急了！！！
: 
: 【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: : 这个不属于图论，属于计算几何

────────────────────────────────────────
 xiong (还没想好)                     于 2003年01月03日17:13:27 星期五 说道:

算法版有一点资料，自己去找吧
//zju1010还没有做出来呢
【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 我搞不定这个东西，以前做过一部分，后来由于难度太大，放弃了
: 找找计算几何相关的书籍就行了
: 【 在 zealous (zealous) 的大作中提到: 】
: : 是否可以搞定？？？？？
: : 有没有相关书籍？！？？
: : 最好直接给出源代码！！！

────────────────────────────────────────
 syteek ([四爷]·[我爱公社])          于 2003年01月03日17:14:42 星期五 说道:

距离最远的两端端点之间的线段来代替重合的线段
【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 这个情况就需要剔除掉，可以当成一条线段处理
: 【 在 ggyy (胖子·理想情感在心中沉淀，梦在飞扬) 的大作中提到: 】
: :     对呀，忘了相交的情况了
: :     要是线段有重合的算不算一个闭合的图形？

────────────────────────────────────────
 syteek ([四爷]·[我爱公社])          于 2003年01月03日17:16:52 星期五 说道:

【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: 
: 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
                               ~~~~~~~~~~~~~~~~~~这个思路是是行的通的。
但是刚才我在考虑若各个线段交于一点的时候想不下去了。如果封闭的图形
不止一个怎么判断？
: 
: 
: yes !!!???????
: 
: 【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: : 需要搜一下，如果这东西不重要的话，建议你别做了

────────────────────────────────────────
 fobcaesar (温泉企鹅)〓(欢喜的慈雨)   于 2003年01月03日17:56:14 星期五 说道:

先要把所有的端点找到，也就是所有线段的交点 
【 在 syteek ([四爷]·[我爱公社]) 的大作中提到: 】
: 【 在 zealous (zealous) 的大作中提到: 】
: : 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: : 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
:                                ~~~~~~~~~~~~~~~~~~这个思路是是行的通的。
: 但是刚才我在考虑若各个线段交于一点的时候想不下去了。如果封闭的图形
: 不止一个怎么判断？

────────────────────────────────────────
 zealous (zealous)                    于 Fri Jan  3 18:30:00 2003) 说道:


这个已经想到了，但是，往下！！……………

【 在 fobcaesar (温泉企鹅)〓(欢喜的慈雨) 的大作中提到: 】
: 先要把所有的端点找到，也就是所有线段的交点 
: 【 在 syteek ([四爷]·[我爱公社]) 的大作中提到: 】
: : 【 在 zealous (zealous) 的大作中提到: 】
: : : 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: : : 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
: :                                ~~~~~~~~~~~~~~~~~~这个思路是是行的通的。 ..

: : 但是刚才我在考虑若各个线段交于一点的时候想不下去了。如果封闭的图形
: : 不止一个怎么判断？



────────────────────────────────────────
 Pomegranate (石榴哥-=|863-05|=-)     于 2003年01月04日13:59:00 星期六 说道:

不是图论问题！
把所有线段画在屏幕上，对每条的两侧进行两次
蔓延填色，如果某次没有染到屏幕四角，就有闭合图形。
嘿嘿
【 在 zealous (zealous) 的大作中提到: 】
: 
: 
: 各位学过数据结构吗？好像里边的图论可以解决这个问题。
: 
: 可以遍历一个图，看看是否可以从起点回到“起点”？？？？ ？
: 
: 
: yes !!!???????
: 
: 【 在 Pomegranate (石榴哥-=|863-05|=-) 的大作中提到: 】
: : 需要搜一下，如果这东西不重要的话，建议你别做了

────────────────────────────────────────