#include<iostream>
using namespace std;
#define MAX_N 1020
#define INFINITE 1000000

struct Platform
{
	int l, r, h;
}; Platform platform[MAX_N];

int cmp( const void *a ,const void *b)  
{  
	return (*(Platform *)b).h > (*(Platform *)a).h ? 1 : -1;         //老天啊。。。。。看了两天 排序排反了。。。
}  



int main()
{
	int i, j;
	int t, N, X, Y, MAX;
	bool used[MAX_N][2];
	int leftmin[MAX_N], rightmin[MAX_N];
	int temp, sign;

	cin >> t;
	while(t --) {
		cin >> N >> X >> Y >> MAX;
		platform[0].h = Y;
		for(i = 1; i <= N; i ++)   //从1开始
			cin >> platform[i].l >> platform[i].r >> platform[i].h;
		qsort(platform, N + 1, sizeof(platform[0]), cmp);

		memset(used, 0, sizeof(used));
		//memset(leftmin, 0, sizeof(leftmin));      //大失误。。。怎么能初始化0.。。应该为一个大值
		//memset(rightmin, 0, sizeof(rightmin));
		for(i = 1; i < N + 2; i ++)
			leftmin[i] = rightmin[i] = INFINITE;
		platform[0].l = platform[0].r = X;     //初始坐标为给定的X 
	
		platform[N + 1].h = 0;                 //地面高度为0
		platform[N + 1].l = -INFINITE;
		platform[N + 1].r = INFINITE;     //地面左右界为无穷
		leftmin[0] = rightmin[0] = 0;
		for(i = 0; i <= N; i ++) {
			for(j = i + 1; j <= N + 1; j ++) {
				if(!used[i][0]) {          // used[][0]为左 [][1]为右
					if(platform[i].l > platform[j].l && platform[i].l <= platform[j].r) {
						if(platform[i].h - platform[j].h > MAX)
							leftmin[i] = INFINITE;
						else {
							temp = leftmin[i] + platform[i].l - platform[j].l;
							if(temp < leftmin[j])
								leftmin[j] = temp;
							temp = leftmin[i] + platform[j].r - platform[i].l;
							if(temp < rightmin[j])
								rightmin[j] = temp;
						}		
						used[i][0] = 1;
					}
				}
				if(!used[i][1]) {
					if(platform[i].r < platform[j].r && platform[j].l <= platform[i].r) {
						if(platform[i].h - platform[j].h > MAX)
							rightmin[i] = INFINITE;
						else {
							temp = rightmin[i] + platform[i].r - platform[j].l;
							if(temp < leftmin[j])
								leftmin[j] = temp;
							temp = rightmin[i] + platform[j].r - platform[i].r;
							if(temp < rightmin[j])
								rightmin[j] = temp;
						}	
						used[i][1] = 1;
					}
				}
				if(used[i][0] && used[i][1])        // i + 1继续循环
					break;
			}
		}
		//for(i = 0; i <= N; i ++) {
		//	cout << "leftmin" << leftmin[i] << endl;
		//}
		int minl = leftmin[N];          //输出
		int minr = rightmin[N];
		for(i = 0; i < N; i ++) {
			sign = 0;
			for(j = i + 1; j <= N; j ++) {
				if(platform[i].l > platform[j].l && platform[i].l < platform[j].r) {
					sign = 1;
					break;
				}
			}
			//cout <<">>>"<< leftmin[i] << endl;
			if(sign == 0) {
				if(minl > leftmin[i])
					minl = leftmin[i];
			}
		}
		for(i = 0; i < N; i ++) {
			sign = 0;
			for(j = i + 1; j <= N; j ++) {
				if(platform[i].r > platform[j].l && platform[i].r < platform[j].r) {
					sign = 1;
					break;
				}
			}
			if(sign == 0) {
				if(minr > rightmin[i])
					minr = rightmin[i];
			}
		}
		if(minl > minr)
			cout << minr + Y << endl;
		else
			cout << minl + Y << endl;
	}
	return 0;
}

• Прикольные форумы (1593) lolittacka 2011-10-21 13:04:20
• personal vaporizer (1743) iromialerne 2013-03-12 01:36:59
• vaporizer gun dx4 (1817) iromialerne 2013-03-12 01:37:01
• vaporizer vs smoking (2100) iromialerne 2013-03-12 04:57:11
• universal vaporizer combo mm (2510) iromialerne 2013-03-12 05:03:43
• vaporizer usage (1446) iromialerne 2013-03-12 05:03:59