3812064_ac_250ms_224k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

struct point
{
	double x, y;
	point (double _x, double _y) : x (_x), y (_y) {}
	point () {}
};

struct segment
{
	point a, b;
	segment (point _a, point _b) : a (_a), b (_b) {}
	segment () {}
};

double max(double a,double b)
{
	return a > b ? a : b;
}

double min(double a,double b)
{
	return a < b ? a : b;
}

double multi(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool isIntersected(point s1,point e1,point s2,point e2)
{

    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 n, ans;
segment way;
segment seg[30];

void calc()
{
	int i, num (1);

	for (i = 0; i < n; i++)
	{
		if (isIntersected(way.a, way.b, seg[i].a, seg[i].b))
		{
			num++;
		}
	}
	if (num < ans)
		ans = num;
}

int main()
{
	int i;
	double x1, y1, x2, y2;

	scanf("%d", &n);
	ans = n + 1;
	for (i = 0; i < n; i++)
	{
		scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
		seg[i] = segment(point(x1, y1), point(x2, y2));
	}
	scanf("%lf%lf", &x1, &y1);
	way.a = point(x1, y1);
	for (x1 = 0.0; x1 <= 100.0; x1 += 0.1)
	{
		way.b.x = x1;
		way.b.y = 0;
		calc();
		way.b.x = x1;
		way.b.y = 100;
		calc();
		way.b.x = 0;
		way.b.y = x1;
		calc();
		way.b.x = 100;
		way.b.y = x1;
		calc();
	}
	printf("Number of doors = %d\n", ans);
	return 0;
}