题目链接：http://codeforces.com/problemset/problem/589/D
题意：给出n个人行走的开始时间和结束时间，求每个人分别能跟多少人相遇打招呼。
分析：两个人行走无非四种情况，同向两种：-> -> 和 <- <-反向两种-> <- 和<- ->分情况推他们相遇的条件即可，我是列方程求解的。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> #include<queue> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int maxt = 1e6 + 10; const double eps = 0.00000000000001; const int inf = 0x3f3f3f3f; struct person { int num,t,b,e,time; }p[maxn]; int hellow[maxn]; bool check1(int a,int b, int c, int d)//看区间[a,b]与区间[c,d]是否有交集 { if(c <= a && b <= d) return true; if(a <= c && c <= b) return true; if(a <= d && d <= b) return true; return false; } bool check2(double t1, double t11, double t2, double t22, double t)//判断t是否同时在区间[t1,t2]和区间[t11,t22]内 { return t >= t1 && t <= t11 && t >= t2 && t <= t22; } int main() { int k; while(~scanf("%d",&k)) { memset(hellow, 0, sizeof(hellow)); memset(p, 0, sizeof(p)); for(int i = 0; i < k; i++) { scanf("%d%d%d",&p[i].t, &p[i].b, &p[i].e); } for(int i = 0; i < k; i++)//两两看是否相遇 { for(int j = i + 1; j < k; j++) { int t1 = p[i].t, t11 = p[i].t + abs(p[i].e - p[i].b);//t1:第i个人开始的时间 t11:第i个人结束的时间 int t2 = p[j].t, t22 = p[j].t + abs(p[j].e - p[j].b);//同上 int fi = p[i].b <= p[i].e ? 1 : -1; int fj = p[j].b <= p[j].e ? 1 : -1; int b1 = p[i].b, e1 = p[i].e, b2 = p[j].b, e2 = p[j].e; if(fi == 1 && fj == 1)//-> -> { if(t1 - b1 == t2 - b2 && check1(t1,t11,t2,t22)) { hellow[i]++,hellow[j]++; } } if(fi == 1 && fj == -1)//-> <- { double t = (double)(t1 - b1 + t2 + b2); t /= 2; if(check2(t1,t11,t2,t22,t)) { hellow[i]++,hellow[j]++; } } if(fi == -1 && fj == 1)//<- -> { double t = (double)(t1 + b1 + t2 - b2); t /= 2; if(check2(t1,t11,t2,t22,t)) { hellow[i]++,hellow[j]++; } } if(fi == -1 && fj == -1)//<- <- { if(t1 + b1 == t2 + b2 && check1(t1,t11,t2,t22)) { hellow[i]++,hellow[j]++; } } } } for(int i = 0; i < k; i++) { if(i) printf(" "); printf("%d",hellow[i]); } printf("\n"); } return 0; }