苗火 Nicholas

Description

Dr. Shelden最近制造了一种新机器人，现在他要开始给他的机器人做一些简单训练啦。

Shelden在实验室的地面上铺了一些箭头，这些箭头可以看成是二维平面上的一些有向线段，而且都是水平线段或垂直线段，将这些线段从1开始编号，机器人一开始在第1条线段的起点处。现在shelden要写一个程序让他的机器人能够规划一条最短的路径按编号顺序从小到大通过所有的有向线段(只有从线段的起点走到终点才算通过)。机器人每次都只能做90°转弯，而且由于每次转弯都将耗费很大能量，所以shelden希望所求路径的转弯总次数最少。比如在下面这个例子中，实验室的地面上有5个箭头，最少就需要11次拐弯才能将5条线段串起来。

Input

第一行为一个整数T，表示数据的组数。每组数据的第一行为一个整数N(1<N<100)，表示有向线段的条数。接下来N行，第i行表示编号为i的有向线段。每行有4个整数x1，y1，x2，y2，(-1000≤x1,y1,x2,y2≤1000) 分别表示有向线段的起点a(x1,y1)和终点b(x2,y2)。数据保证所有线段长度大于0，线段之间可以交叉，但不会互相重叠（端点除外）。

Output

每组样例输出两个整数表示所求路径的最小长度和最小转弯次数。

#include <stdio.h>

void main(){
	int t,n,x1,y1,x2,y2, xx1, yy1, xx2, yy2, start;
	int dist, turns;
	int dx,dy, dxx, dyy, dxxx, dyyy;

	scanf(" %d", &t);
	while(t--){
		scanf(" %d", &n);
		dist = 0;
		turns = 0;
		start = 1;
		while(n--){
			scanf(" %d %d %d %d", &x1, &y1, &x2, &y2);
			if(start){
				start = 0;
			}else{
				/* From the second arrow */
				dx = xx2 - xx1;
				dy = yy2 - yy1;

				dxx = x1 - xx2;
				dyy = y1 - yy2;

				dist += abs(dx) + abs(dy) + abs(dxx) + abs(dyy);

				if(dx != 0){
					if(dx * dxx >= 0){
						if(dyy != 0){
							dyyy = dyy;
							dxxx = 0;
							turns+=1;
						}else{
							dyyy = 0;
							dxxx = dxx;
						}
					}else{
						dyyy = 0;
						dxxx = dxx;
						turns+=2;
					}
				}else{
					if(dy * dyy >= 0){
						if(dxxx != 0){
							dxxx = dxx;
							dyyy = 0;
							turns+=1;
						}else{
							dxxx = 0;
							dyyy = dyy;
						}
					}else{
						dxxx = 0;
						dyyy = dyy;
						turns+=2;
					}
				}

				dxx = x2 - x1;
				dyy = y2 - y1;
	
				if(dxx * dxxx != 0){
					if(dxx * dxxx > 0){
						/* nop */
					}else{
						turns+= 2;
					}
				}else if(dyy * dyyy != 0){
					if(dyy * dyyy > 0){
						/* nop */
					}else{
						turns+=2;
					}
				}else{
					turns += 1;
				}

			}
			xx1 = x1; yy1 = y1; xx2 = x2; yy2 = y2;		
		}
		dist += abs(dxx) + abs(dyy);
		printf("%d %d\n", dist, turns);
	}
}