今天比赛的时候略坑， admin告诉我询问Q的个数不超过n^2, 赛后敲了个 O(Q*m^3)的复杂度，但这个复杂度常数比较低，可能在除以个小常数， 300ms过了，真心无语，数据应该水了吧，比赛的时候已经想到了，但怕超时没敢敲。
这次的题解好坑， 说什么是要用什么图做，真心蛋疼，搞得这么高端干什么，看懂了它的思路，代码写起来不好写，至少我是这样的。
我的做法：
先预处理出每两个station之间的中垂线。
对于每个询问，判断每条中垂线与询问的两城市之间的连线是否相交(设交点P)。
当然相交也不一定说明交点是 信号改变的点，因为2个station的点可能不是距离P最近的点，我们要判其它station与P点的距离是否小于这两个station的距离，
如果是那么这条中垂线就是无效的，其它都是有效的，ans++。
代码：
#include <cstdio>
#include <cmath>
const double eps = 1e-8;
inline int dcmp(double x) {
if(fabs(x) < eps) return 0;
return x > eps ? 1 : -1;
}
struct point {
double x, y;
point(double x, double y) :
x(x), y(y) {
}
point() {
}
point operator+(const point &t) const {
return point(x + t.x, y + t.y);
}
point operator-(const point &t) const {
return point(x - t.x, y - t.y);
}
point operator*(const double &t) const {
return point(x*t, y*t);
}
inline void in() {
scanf("%lf%lf", &x, &y);
}
} sta[55], city[55], tt, tp;
struct line {
point a, b;
line(point a, point b) :
a(a), b(b) {
}
line() {
}
} l[50][50];
int n, m, k;
inline line getMidLine(const point &a, const point &b) {
point mid = (a + b) *0.5;
point tp = b-a;
return line(mid, mid+point(-tp.y, tp.x));
}
inline double cross(const point &a, const point &b) {
return a.x*b.y-a.y*b.x;
}
inline point intersect(const point &a, const point &b, const point &l, const point &r) {
point ret = a;
double t = ((a.x - l.x) * (l.y - r.y) - (a.y - l.y) * (l.x - r.x))
/ ((a.x - b.x) * (l.y - r.y) - (a.y - b.y) * (l.x - r.x));
ret.x += (b.x - a.x) * t;
ret.y += (b.y - a.y) * t;
return ret;
}
inline bool dotOnSeg(const point &p, const point &l, const point &r) { //判点在线段上
return (p.x-l.x)*(p.x-r.x) < eps
&& (p.y-l.y)*(p.y-r.y) < eps;
}
inline double dis(const point &a, const point &b) {
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
inline bool judge(const point &p, int &a) {
double d = dis(p, sta[a]);
int i;
for(i = 0; i < m; i++) if(i != a)
if(d > dis(p, sta[i])+eps) return 0;
return 1;
}
int a, b, ans;
int main() {
int i, j;
while (~scanf("%d%d", &n, &m)) {
for (i = 0; i < n; i++) city[i].in();
for (i = 0; i < m; i++) sta[i].in();
for (i = 0; i < m; i++)
for (j = i + 1; j < m; j++)
l[i][j] = getMidLine(sta[i], sta[j]);
scanf("%d", &k);
while(k--) {
ans = 0;
scanf("%d%d", &a, &b);
a--; b--;
tt = city[a]-city[b];
for(i = 0; i < m; i++)
for(j = i+1; j < m; j++) {
if(!dcmp(cross(tt, l[i][j].a-l[i][j].b))) continue;
tp = intersect(city[a], city[b], l[i][j].a, l[i][j].b);
if(dotOnSeg(tp, city[a], city[b]))
ans += judge(tp, i);
}
printf("%d
", ans);
}
}
return 0;
}