#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct
{
	double x;
	double y;
}Point;

typedef struct
{
	Point pt1;
	Point pt2;
}Segment;

Point pt;
double left[100],right[100],top[100],bottom[100];
Point mid[1000];
Segment sgmt[31];

double multi(Point p1, Point p2, Point p0)
{
    //求矢量[p0, p1], [p0, p2]的叉积
    //p0是顶点 
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    //若结果等于0，则这三点共线
    //若结果大于0，则p0p2在p0p1的逆时针方向
    //若结果小于0，则p0p2在p0p1的顺时针方向 
}

double max(double x, double y)
{
    //比较两个数的大小，返回大的数
    return  x > y ? x : y;
}

double min(double x, double y)
{
    //比较两个数的大小，返回小的数
	return  x < y ? x : y;
}

bool isIntersected(Point s1, Point e1, Point s2, Point e2)
{
    //判断线段是否相交
    //1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交 
    //2.跨立试验
    if(
    (max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
    (max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
    (max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
    (max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
    (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
    (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
    )  
		return true;
    
    return false;    
}

int main()
{
	int n,i,j;
	int lf = 1,rt = 1,tp = 1,btm = 1;
	int counter = 0;
	int res,min = 99999999;

	left[0] = 0;
	right[0] = 0;
	top[0] = 0;
	bottom[0] = 0;

	scanf("%d",&n);
	for(i = 0; i < n; i ++)
	{
		scanf("%lf%lf",&pt.x,&pt.y);
		sgmt[i].pt1.x = pt.x;
		sgmt[i].pt1.y = pt.y;
		if(pt.x == 0)
			left[lf++] = pt.y;
		if(pt.x == 100)
			right[rt++] = pt.y;
		if(pt.y == 0)
			bottom[btm++] = pt.x;
		if(pt.y == 100)
			top[tp++] = pt.x;
		scanf("%lf%lf",&pt.x,&pt.y);
		sgmt[i].pt2.x = pt.x;
		sgmt[i].pt2.y = pt.y;
		if(pt.x == 0)
			left[lf++] = pt.y;
		if(pt.x == 100)
			right[rt++] = pt.y;
		if(pt.y == 0)
			bottom[btm++] = pt.x;
		if(pt.y == 100)
			top[tp++] = pt.x;
	}
	scanf("%lf%lf",&pt.x,&pt.y);//宝物的坐标

	left[lf++] = 100;
	right[rt++] = 100;
	top[tp++] = 100;
	bottom[btm++] = 100;

	sort(left,left+lf);
	sort(right,right+rt);
	sort(top,top+tp);
	sort(bottom,bottom+btm);

	for(i = 0; i < lf-1; i++)//求中点
	{
		mid[counter].x = 0;
		mid[counter].y = ( left[i] + left[i+1] ) / 2;
		counter++;
	}
	for(i = 0; i < rt-1; i++)
	{
		mid[counter].x = 100;
		mid[counter].y = ( right[i] + right[i+1] ) / 2;
		counter++;
	}
	for(i = 0; i < tp-1; i++)
	{
		mid[counter].y = 100;
		mid[counter].x = ( top[i] + top[i+1] ) / 2;
		counter++;
	}
	for(i = 0; i < btm-1; i++)
	{
		mid[counter].y = 0;
		mid[counter].y = ( bottom[i] + bottom[i+1] ) / 2;
		counter++;
	}

	for(i = 0; i < counter; i++)
	{
		printf("%lf    %lf\n",mid[i].x,mid[i].y);
		res = 0;
		for(j = 0; j < n; j++)
		{
			if(isIntersected(sgmt[j].pt1,sgmt[j].pt2,pt,mid[i]))
				res++;
		}
		if(res < min)
			min = res;
	}

	printf("Number of doors = %d\n",min+1);
	return 0;
}

• Re:Why wrong answer??有测试数据吗 (3234) harkue 2007-08-09 20:47:24