题意：
有b个炸弹，p个飞机，平行于x轴飞行，地面部署了m个导弹，只能垂直打。知道0时刻炸弹、飞机的坐标，以及导弹的坐标以及炸弹、导弹、飞机的速度，问不打到飞机的情况下最多能拦截多少导弹？
给力条件：炸弹被导弹击中后，继续飞行，而导弹立刻消失。飞行物高度均不同
有个注意点：注意C++中的短路问题，慎用两个函数相或、与，可能因此一个函数得不到执行，这个在线段树里是很麻烦的。宁可多写一步
解法：
上次比赛这题死都A不掉，今天重新做了下，1A。。
首先，看到这题肯定想到二分图的匹配模型。这个不细说，说下之前的处理。
首先，按照飞行物高度排序，然后枚举导弹i能否打到j个炸弹，计算该导弹打到每个飞行物的时间区间，看区间有没有被完全覆盖即可判断。这里用到线段树。然后就是可恶的精度问题，其实，这题完全能够避免精度误差，将所有坐标预先乘以三种速度的最小公倍数，然后离散化再用线段树来统计就没问题了。区间处理还要注意一点就是处理成左闭右开区间，用[s*2,e*2-1)即可。
代码：
1
# include <cstdio>
2# include <algorithm>
3# include <vector>
4# include <cstring>
5using namespace std;
6struct graph
7
{
8
int g[305],nxt[305*305],v[305*305],c,match[605];
9 bool used[305];
10 void clear()
11
{
12 memset(g,-1,sizeof(g));
13 memset(match,-1,sizeof(match));
14 c=0;
15
}
16 void insert(int s,int e)
17 {
18 v[c]=e;
19 nxt[c]=g[s];
20 g[s]=c++;
21 }
22 bool dfs(int pos)
23 {
24 if(used[pos]) return false;
25 used[pos]=true;
26 for(int p=g[pos];p!=-1;p=nxt[p])
27 if(match[v[p]]==-1||dfs(match[v[p]]))
28 {
29 match[v[p]]=pos;
30 return true;
31 }
32 return false;
33 }
34 int Match(int n)
35 {
36 int res=0;
37 for(int i=0;i<n;i++)
38 {
39 memset(used,false,sizeof(used));
40 res+=dfs(i);
41 }
42 return res;
43 }
44
}g;
45struct st_tree
46{
47 struct node
48 {
49 int s,e;
50 bool cover;
51 }st[10000];
52 int mid(int s,int e)
53 {
54 return (s+e)>>1;
55 }
56 void init(int s,int e,int pos=1)
57 {
58 st[pos].s=s;
59 st[pos].e=e;
60 st[pos].cover=false;
61 if(e!=s+1)
62 {
63 init(s,mid(s,e),pos<<1);
64 init(mid(s,e),e,(pos<<1)+1);
65 }
66 }
67 void clear()
68 {
69 init(0,2500);
70 }
71 bool insert(int s,int e,int pos=1)
72 {
73 if(st[pos].cover) return false;
74 if(st[pos].s==s&&st[pos].e==e)
75 {
76 st[pos].cover=true;
77 return true;
78 }
79 else if(e<=mid(st[pos].s,st[pos].e))
80 return insert(s,e,pos<<1);
81 else if(s>=mid(st[pos].s,st[pos].e))
82 return insert(s,e,(pos<<1)+1);
83 else
84 {
85 bool a1=insert(s,mid(st[pos].s,st[pos].e),pos<<1),a2=insert(mid(st[pos].s,st[pos].e),e,(pos<<1)+1);
86 return a1||a2;
87 }
88 }
89}refer;
90struct node
91{
92 long long x,y;
93 bool type;
94 bool operator<(const node &pos) const
95 {
96 return y<pos.y;
97 }
98};
99int b,p,m;
100node barr[1000];
101long long miss[400];
102int vb,vp,vm;
103long long s[1500],sc=0;
104int gcd(int a,int b)
105{
106 int t;
107 while(b) t=a%b,a=b,b=t;
108 return a;
109}
110int main()
111{
112 int test;
113 scanf("%d",&test);
114 for(int tt=1;tt<=test;tt++)
115 {
116 scanf("%d%d%d%d%d%d",&b,&p,&m,&vb,&vp,&vm);
117 long long lcd=(long long)vb*vp*vm/gcd(vb,gcd(vp,vm));
118 for(int i=0;i<b;i++)
119 {
120 barr[i].type=0;
121 scanf("%lld%lld",&barr[i].x,&barr[i].y);
122 barr[i].x*=lcd;
123 barr[i].y*=lcd;
124 }
125 for(int i=b;i<b+p;i++)
126 {
127 barr[i].type=1;
128 scanf("%lld%lld",&barr[i].x,&barr[i].y);
129 barr[i].x*=lcd;
130 barr[i].y*=lcd;
131 }
132 for(int i=0;i<m;i++)
133 {
134 scanf("%lld",miss+i);
135 miss[i]*=lcd;
136 }
137 sort(barr,barr+b+p);
138 g.clear();
139 for(int i=0;i<m;i++)
140 {
141 sc=0;
142 for(int j=0;j<b+p;j++)
143 {
144 long long ss=(miss[i]-barr[j].x)/(barr[j].type?vp:vb)-barr[j].y/vm,ee=(miss[i]-barr[j].x+lcd)/(barr[j].type?vp:vb)-barr[j].y/vm;
145 if(ee<0) continue;
146 if(ss<0) ss=0;
147 s[sc++]=ss;
148 s[sc++]=ee;
149 }
150 sort(s,s+sc);
151 sc=unique(s,s+sc)-s;
152 refer.clear();
153 for(int j=0;j<b+p;j++)
154 {
155 long long ss=(miss[i]-barr[j].x)/(barr[j].type?vp:vb)-barr[j].y/vm,ee=(miss[i]-barr[j].x+lcd)/(barr[j].type?vp:vb)-barr[j].y/vm;
156 if(ee<0) continue;
157 if(ss<0) ss=0;
158 ss=(lower_bound(s,s+sc,ss)-s)*2;
159 ee=(lower_bound(s,s+sc,ee)-s)*2+1;
160 if(barr[j].type) refer.insert(ss,ee);
161 else if(refer.insert(ss,ee)) g.insert(i,j);
162 }
163
164 }
165 printf("Mission #%d: %d bomber(s) exploded\n",tt,g.Match(m));
166 }
167 return 0;
168}
169