This post is written in Chinese. Please consider using Google Translate

把每个订单看作一个顶点，两个订单a,b，完成a后能在b开始之前赶到b，则向a,b连接一条有向边。在图中求最小路径覆盖即可，转化为二分图最大匹配。

/* 
 * Problem: pku2060 Taxi Cab Scheme
 * Author: Guo Jiabao
 * Time: 2009.4.8 14:29
 * State: Solved
 * Memo: 最小路径覆盖
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=501*2*2,MAXL=201;
using namespace std;
struct quest
{
    int r,sx,sy,dx,dy;
}P[MAXN];
struct edge
{
    edge *next;
    int t;
}ES[MAXN*MAXN];
edge *V[MAXN];
bool vis[MAXN];
int N,EC=-1,Ans,Match[MAXN];
inline int cmp(const void *a,const void *b)
{
    return ((quest *)a)->r - ((quest *)b)->r;
}
inline int babs(int a){return a>0?a:-a;}
inline int dist(int x1,int y1,int x2,int y2)
{
    return babs(x1-x2)+babs(y1-y2);
}
inline bool canreach(int a,int b)
{
    int r1=dist(P[a].sx,P[a].sy,P[a].dx,P[a].dy);
    int r2=dist(P[a].dx,P[a].dy,P[b].sx,P[b].sy);
    return r1+r2<P[b].r-P[a].r;
}
inline void addedge(int a,int b)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC;V[a]->t=b;
}
void init()
{
    int i,j,h,m;
    EC=-1;
    scanf("%d",&N);
    memset(V,0,sizeof(V));
    for (i=1;i<=N;i++)
    {
        scanf("%d:%d%d%d%d%d",&h,&m,&P[i].sx,&P[i].sy,&P[i].dx,&P[i].dy);
        P[i].r=h*60+m;
    }
    qsort(P+1,N,sizeof(P[0]),cmp);
    for (i=1;i<N;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            if (canreach(i,j))
                addedge(i,j+N);
        }
    }
}
bool path(int i)
{
    for (edge *k=V[i];k;k=k->next)
    {
        int j=k->t;
        if (!vis[j])
        {
            vis[j]=true;
            if (Match[j]==0 || path(Match[j]))
            {
                Match[j]=i;
                return true;
            }
        }
    }
    return false;
}
void hungary()
{
    int i,mat=0;
    memset(Match,0,sizeof(Match));
    for (i=1;i<=N;i++)
    {
        memset(vis,0,sizeof(vis));
        if (path(i))
            mat++;
    }
    Ans=N-mat;
}
int main()
{
    int i,T;
    freopen("texi.in","r",stdin);
    freopen("texi.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        hungary();
        printf("%dn",Ans);
    }
    return 0;
}