3945948_tle.cpp

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

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

double hx1, hx2, hy;
double px1, px2, py;

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



struct line
{
	double a, b, c;
};

struct segment
{
	double l, r;
	segment(double _l, double _r) : l (_l), r (_r) {}

	bool operator < (const segment &s)	const
	{
		if (l != s.l)
			return l < s.l;
		return r < s.r;
	}
};

vector <segment> p;

line LineFromSeg(point a,point b)
{
	line l;
	
	l.a = b.y - a.y;
	l.b = a.x - b.x;
	l.c = b.x * a.y - a.x * b.y;
	return l;
}

double get(point a, point b)
{
	line l = LineFromSeg(a, b);
	return -(l.c + l.b * py) / l.a;
}

int main()
{
	int i, j, n;
	double x1, x2, y;
	double last;
	double max;

	while (true)
	{
		scanf("%lf%lf%lf", &hx1, &hx2, &hy);
		p.clear();
		if (hx1 == 0 && hx2 == 0 && hy == 0)
		{
			break;
		}
		point a (hx1, hy);
		point b (hx2, hy);
		scanf("%lf%lf%lf", &px1, &px2, &py);
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%lf%lf%lf", &x1, &x2, &y);
			p.push_back(segment(get(point(x1, y), b), get(point(x2, y), a)));
		}
		sort(p.begin(), p.end());
		last = px1;
		max = -1;
		for (i = 0; i < p.size(); i++)
		{
			j = i;
			if (p[i].l - last > max)
				max = p[i].l - last;
			while (j < p.size() && p[j].l <= p[i].r)
			{
				if (p[j].r > last)
					last = p[j].r;
				j++;
			}
			i = j - 1;
		}
		if (px2 - last > max)
			max = px2 - last;
		if (max <= 0)
			printf("No View\n");
		else
			printf("%.2lf\n", max);
	}
	return 0;
}