HDU 2150 Pipe（判断线段相交水）

**链接：****传送门 **

题意：略

思路：数据量很小，直接暴力所有线段

/*************************************************************************

    > File Name: hdu2150.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月07日 星期日 23时09分58秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

#define eps 1e-10

struct point{ double x,y; };

bool inter(point a,point b,point c,point d){

	if( min(a.x,b.x) > max(c.x,d.x) ||

		min(a.y,b.y) > max(c.y,d.y) ||

		min(c.x,d.x) > max(a.x,b.x) ||

		min(c.y,d.y) > max(a.y,b.y)	)	return 0;

	double h , i , j , k;

	h = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);

	i = (b.x - a.x)*(d.y - a.y) - (b.y - a.y)*(d.x - a.x);

	j = (d.x - c.x)*(a.y - c.y) - (d.y - c.y)*(a.x - c.x);

	k = (d.x - c.x)*(b.y - c.y) - (d.y - c.y)*(b.x - c.x);

	return h*i<=eps && j*k<=eps;

}

int main(){

	int N,num[31];

	point pi[31][101];

	while(~scanf("%d",&N)){

		for(int i=0;i<N;i++){

			scanf("%d",&num[i]);

			for(int j=0;j<num[i];j++){

				scanf("%lf%lf",&pi[i][j].x,&pi[i][j].y);

			}

		}

		bool ok = false;

		for(int i=0;i<N;i++){

			for(int j=i+1;j<N;j++){

				for(int k=0;k<num[i]-1;k++){

					for(int s=0;s<num[j]-1;s++){

						if( inter(pi[i][k],pi[i][k+1],pi[j][s],pi[j][s+1])){

							ok = true;	break;

						}

					}

				}

			}

		}

		if(ok)	printf("Yes\n");

		else	printf("No\n");

	}

	return 0;

}

巴特西

HDU 2150 Pipe（判断线段相交水）

最新文章

热门文章

巴特西

HDU 2150 Pipe（ 判断线段相交水 ）

最新文章

热门文章

HDU 2150 Pipe（判断线段相交水）