hdu2150 Pipe (判断线段是否相交)

Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)

​

Total Submission(s): 1572Accepted Submission(s): 603

Problem Description

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

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

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

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

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

Input

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

Output

对于每组测试，如果该测试管道与管道之间有相交的话，输出"Yes"，否则输出"No"。

Sample Input

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

Sample Output

Yes No No

Author

Linle

Source

​​ACM程序设计期末考试——2008-01-02（3 教417）​​

Recommend

lcy|We have carefully selected several similar problems for you: ​​1558​​​ ​​​1374​​​ ​​​2907​​​ ​​​1883​​​ ​​​2297​​

解析：枚举任意两条折线上的线段，判断他们是否相交。

这道题坐标得用 long long，不知道为什么，反正我用 int 错了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;
const int maxn1=30;
const int maxn2=100;
int s[maxn1+10];
struct tnode{
  LL x,y;
}p[maxn1+10][maxn2+10];

LL crossprod(tnode a,tnode b,tnode c)
{
  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool intersect(tnode a,tnode b,tnode c,tnode 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,b,d)<=0 &&
   crossprod(c,d,a)*crossprod(c,d,b)<=0)return 1;
  return 0;
}

bool ok(int n)
{
  int k1,k2,i,j;
  for(k1=1;k1<n;k1++)
    for(k2=k1+1;k2<=n;k2++)
      for(i=1;i<s[k1];i++)
        for(j=1;j<s[k2];j++)
          if(intersect(p[k1][i],p[k1][i+1],p[k2][j],p[k2][j+1]))return 1;
  return 0;
}

int main()
{
  freopen("1.in","r",stdin);

  int n,i,j;
  while(scanf("%d",&n)!=EOF)
    {
      for(i=1;i<=n;i++)
        {
          scanf("%d",&s[i]);
          for(j=1;j<=s[i];j++)
            scanf("%I64d%I64d",&p[i][j].x,&p[i][j].y);
    }
      if(n==1)printf("No\n");
      else printf("%s\n",ok(n)?"Yes":"No");
  }
  return 0;
}