首页 > ACM题库 > HDU-杭电 > hdu 2150 Pipe-几何-[解题报告]C++
2013
12-30

hdu 2150 Pipe-几何-[解题报告]C++

Pipe

问题描述 :

经过激烈的争夺,Lele终于把那块地从Yueyue的手里抢了回来。接下来,Lele要开始建造他的灌溉系统。

通过咨询Lele的好友――化学系的TT,Lele决定在田里挖出N条沟渠,每条沟渠输送一种肥料。

每条沟渠可以看作是一条折线,也就是一系列线段首尾连接而成(除了第一条线段开头和最后一条线段的结尾)。由于沟渠很细,你可以忽略掉它的宽度。

由于不同的肥料之间混合会发生化学反应,所以修建的沟渠与沟渠之间不能相交。

现在TT给Lele画了一些设计图,Lele请你判断一下设计图中的沟渠与沟渠之间是否有相交。

输入:

本题目包含多组测试,请处理到文件结束(EOF)。
每组测试的第一行有一个正整数N(0<N<30),表示管道的数目。接下来给出这N条管道的信息。
对于每条管道,第一行是一个正整数K(0<K<100),表示这条管道是由K个端点组成。
接下来的K行给出这K个端点信息。每个端点占一行,用两个整数X和Y(0<X,Y<1000)分别表示这个端点的横坐标和纵坐标的值。

输出:

本题目包含多组测试,请处理到文件结束(EOF)。
每组测试的第一行有一个正整数N(0<N<30),表示管道的数目。接下来给出这N条管道的信息。
对于每条管道,第一行是一个正整数K(0<K<100),表示这条管道是由K个端点组成。
接下来的K行给出这K个端点信息。每个端点占一行,用两个整数X和Y(0<X,Y<1000)分别表示这个端点的横坐标和纵坐标的值。

样例输入:

2
2
0 0
1 1
2
0 1
1 0
2
2
0 0
1 1
2
1 0
2 1
2
3
0 0
1 1
2 1
2
2 0
3 0

样例输出:

Yes
No
No

/*
 *  题目要求:判断给出的一些折线段是否相交 
 *  解法:枚举每条折线段上的每段线段,判断其是否与其它折线段的线段相交 
 */
 
 #include <cstdio>
 #include <cstdlib>
 #include <iostream>
 
 using  namespace std;
 
 const int N = 35;
 const int M = 105;
 
 int num[N];
 struct point {
     double x;
     double y;
 }p[N][M];
 
 double crossProd(point A, point B, point C) {
     return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
 }
 
 bool segIntersect(point A, point B, point C, point D) {
     if (max(A.x, B.x) >= min(C.x, D.x) &&
         max(C.x, D.x) >= min(A.x, B.x) &&
         max(A.y, B.y) >= min(C.y, D.y) &&
         max(C.y, D.y) >= min(A.y, B.y) &&
         crossProd(A, B, C)*crossProd(A, D, B) > 0 &&
         crossProd(C, D, A)*crossProd(C, B, D) > 0) return true;
     return false;
 }
 
 bool solve(int n) {
     for (int i=0; i<n-1; ++i) {//枚举每条折线段 
         for (int j=1; j<num[i]; ++j) {
             for (int ii=i+1; ii<n; ++ii) {
                 for (int k=1; k<num[ii]; ++k) {
                     if (segIntersect(p[i][j-1], p[i][j], p[ii][k-1], p[ii][k])) return false;//判断线段相交 
                 }
             }
         }
     }
     return true;
 }
 
 int main() {
     int n;
     while (scanf("%d", &n) != EOF) {
         for (int i=0; i<n; ++i) {
             scanf ("%d", &num[i]);
             for (int j=0; j<num[i]; ++j) scanf ("%lf%lf", &p[i][j].x, &p[i][j].y);
         }
         if (n == 1) printf ("No\n");
         else {
             bool yes = solve(n);
             if (yes) printf ("No\n");
             else printf ("Yes\n");
         }    
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/try86/archive/2012/04/24/2468905.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮