4044080_ac_47ms_248k.cpp

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

#include <set>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define ZERO 1e-8
using namespace std;

double h;

double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void calc(double &x1, double &x2, double &x3, double &x4, 
		  double &y1, double &y2, double &y3, double &y4,
		  double tx1, double ty1)
{
	double d = dis(x1, y1, x2, y2);
	double dx = h * (y1 - y2) / d;
	double dy = h * (x2 - x1) / d;

	if (tx1 * (y1 - y2) + ty1 * (x2 - x1) >= 0)
	{
		x3 = x1 + dx, y3 = y1 + dy;
		x4 = x2 + dx, y4 = y2 + dy;
	}
	else
	{
		swap(x1, x2);
		swap(y1, y2);
		x3 = x1 - dx, y3 = y1 - dy;
		x4 = x2 - dx, y4 = y2 - dy;
	}
}

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

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

double multi(double x1, double y1,
			 double x2, double y2,
			 double x3, double y3)
{
    return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
}

bool seg_cross(double x1, double y1, double x2, double y2,
			   double x3, double y3, double x4, double y4)
{
	return 
		max(x1, x2) >= min(x3, x4) &&
		max(x3, x4) >= min(x1, x2) &&
		max(y1, y2) >= min(y3, y4) &&
		max(y3, y4) >= min(y1, y2) &&
		multi(x2, y2, x3, y3, x1, y1) * multi(x2, y2, x4, y4, x1, y1) <= 0 &&
		multi(x4, y4, x1, y1, x3, y3) * multi(x4, y4, x2, y2, x3, y3) <= 0;
}

double area(double x1, double y1, double x2, double y2, double x3, double y3)
{
	double a = dis(x1, y1, x2, y2);
	double b = dis(x1, y1, x3, y3);
	double c = dis(x3, y3, x2, y2);
	double p = (a + b + c) * 0.5;

	return sqrt(p * (p - a) * (p - b) * (p - c));
}

bool inside(double x1, double y1, double x2, double y2,
			double x3, double y3, double x4, double y4,
			double x5, double y5)
{
	return 
		fabs(
			area(x1, y1, x2, y2, x5, y5) +
			area(x1, y1, x3, y3, x5, y5) +
			area(x4, y4, x2, y2, x5, y5) +
			area(x4, y4, x3, y3, x5, y5) -
			dis(x1, y1, x3, y3) * dis(x1, y1, x2, y2)) <= ZERO;
}

bool cross(double x1, double x2, double x3, double x4,
		   double y1, double y2, double y3, double y4,
		   double x5, double y5, double x6, double y6)
{
	return 
		seg_cross(x1, y1, x2, y2, x5, y5, x6, y6) ||
		seg_cross(x1, y1, x3, y3, x5, y5, x6, y6) ||
		seg_cross(x4, y4, x2, y2, x5, y5, x6, y6) ||
		seg_cross(x4, y4, x3, y3, x5, y5, x6, y6) ||
		inside(x1, y1, x2, y2, x3, y3, x4, y4, x5, y5) ||
		inside(x1, y1, x2, y2, x3, y3, x4, y4, x6, y6);
}

int main()
{
	set <int> fall;
	int i, n;
	bool down[100];
	double x[100], y[100], v[100], w[100];
	double x1, x2, x3, x4;
	double y1, y2, y3, y4;
	
	scanf("%d%lf", &n, &h);
	for (i = 0; i < n; i++)
	{
		scanf("%lf%lf%lf%lf", &x[i], &y[i], &v[i], &w[i]);
	}
	memset(down, false, sizeof(down));
	down[0] = true;
	x1 = x[0], y1 = y[0];
	x2 = v[0], y2 = w[0];
	fall.insert(1);
	calc(x1, x2, x3, x4, y1, y2, y3, y4, y1 - y2, x2 - x1);
	while (true)
	{
		bool over = true;
		for (i = 0; i < n; i++)
		{
			if (down[i])
				continue;
			if (cross(x1, x2, x3, x4, y1, y2, y3, y4, x[i], y[i], v[i], w[i]))
			{
				over = false;
				fall.insert(i + 1);
				double tx1 = x1, ty1 = y1, tx2 = x2, ty2 = y2;
				x1 = x[i], x2 = v[i];
				y1 = y[i], y2 = w[i];
				calc(x1, x2, x3, x4, y1, y2, y3, y4, ty1 - ty2, tx2 - tx1);
				down[i] = true;
				break;
			}
		}
		if (over)
		{
			break;
		}
	}
	for (set <int> ::iterator it = fall.begin(); it != fall.end(); ++it)
	{
		printf("%d ", *it);
	}
	puts("");
	return 0;
}