CodeForces

题目链接:http://codeforces.com/problemset/problem/589/D

思路:将每个人的信息转化为自变量为时间因变量为位置的一元方程。再一个个判断是否相遇。

若两人同向，方程相等，如果两人起点与终点有交集则相遇否则不相遇。

若两人反向，求其相遇点，如果该点在两人的起点和终点之间则相遇否则不相遇。

 1 #include<iostream>
 2 using namespace std;
 3 struct node{
 4     double t,s,f,a,b;
 5     int ans;
 6 }p[1005];
 7 int main()
 8 {
 9     int n;
10     cin>>n;
11     for(int i=0;i<n;i++)
12     {
13         cin>>p[i].t>>p[i].s>>p[i].f;
14         if(p[i].s>p[i].f)p[i].a=-1.0;
15         else p[i].a=1.0;
16         p[i].b=p[i].s-p[i].a*p[i].t;
17     }
18     for(int i=0;i<n-1;i++)
19     {
20         for(int j=i+1;j<n;j++)
21         {
22             if(p[i].a==p[j].a&&p[i].b!=p[j].b)continue;
23             else if(p[i].a==p[j].a&&p[i].b==p[j].b)
24             {
25                 double s1=p[i].s,s2=p[j].s,f1=p[i].f,f2=p[j].f;
26                 if(s1<=s2&&f1>=s2||s1>=s2&&s1<=f2||f1<=f2&&s1>=f2||f1>=f2&&f1<=s2)
27                 {
28                     p[i].ans++;
29                     p[j].ans++;
30                 }
31             }
32             else
33             {
34                 double t=(p[i].b-p[j].b)/2.0;
35                 if(t<0)t=-t;
36                 double f1=max(p[i].f,p[i].s),f2=max(p[j].f,p[j].s);
37                 double s1=min(p[i].f,p[i].s),s2=min(p[j].f,p[j].s);
38                 double x1=t*p[i].a+p[i].b,x2=t*p[j].a+p[j].b;
39                 if(x1==x2&&x1>=s1&&x1<=f1&&x2>=s2&&x2<=f2)
40                 {
41                     p[i].ans++;
42                     p[j].ans++;
43                 }
44             }
45         }
46     }
47     for(int i=0;i<n;i++)
48     {
49         if(i!=n-1)cout<<p[i].ans<<" ";
50         else cout<<p[i].ans<<endl;
51     }
52     return 0;
53 }