BZOJ传送门

洛谷传送门

---

解析：

首先，一看到这道题以为不可做啊，考虑怎么用数据结构维护多边形与覆盖的次数？算了洗洗睡吧。。。

思路：

一看到这道题的数据范围只有那么小的一点点，真是。。。

正确思路：反向模拟。 我们要求询问这个位置被多少个多边形覆盖，那么反过来从最终的点翻折，直到最后剩下的合法的点个数就是答案。

那么问题就是怎么把点关于直线对称。

我们考虑求出这个点到这条直线的垂线段向量，然后反向延长一倍就是这个点翻折过去的答案。

求垂线段就是用三角形面积除以这个向量的模长，就是长度，然后乘上原直线的单位法向量。

注意边界情况不算，并随时注意判断点是否仍然在多边形内部（就是判一下在直线左边还是右边）。

然后这道题就变成了一道愉快的$DFS\text{，}O(2^n)$统计答案就行了。

---

代码：

#include<bits/stdc++.h> using namespace std; #define ll long long #define re register #define gc getchar #define pc putchar #define cs const inline double getdb(){ re double x,y=1.0; re char c; re bool f=0; while(!isdigit(c=gc()))if(c=='-')f=1;x=c^48; while(isdigit(c=gc()))x=x*10+(c^48); if(c!='.')return f?-x:x; while(isdigit(c=gc()))x+=(y/=10)*(c^48); return f?-x:x; } cs double eps=1e-6; struct Point{ double x,y; Point(cs double &_x=0,cs double &_y=0):x(_x),y(_y){} friend Point operator+(cs Point &a,cs Point &b){return Point(a.x+b.x,a.y+b.y);} friend Point operator-(cs Point &a,cs Point &b){return Point(a.x-b.x,a.y-b.y);} friend Point operator*(cs Point &a,cs double &b){return Point(a.x*b,a.y*b);} friend Point operator/(cs Point &a,cs double &b){return Point(a.x/b,a.y/b);} friend double operator*(cs Point &a,cs Point &b){return a.x*b.y-b.x*a.y;} friend double dot(cs Point &a,cs Point &b){return a.x*b.x+a.y*b.y;} double norm()cs{return sqrt(dot(*this,*this));} Point reflect()cs{return Point(-y,x)/norm();} }st[10],ed[10]; inline Point reflect(cs Point &p,cs int &i){ double dist=(st[i]-p)*(ed[i]-p)/(st[i]-ed[i]).norm(); return p-(ed[i]-st[i]).reflect()*2*dist; } inline int query(cs Point &p,cs int &now){ if(!now)return p.x>eps&&p.x<100-eps&&p.y>eps&&p.y<100-eps; if((st[now]-p)*(ed[now]-p)<eps)return 0; return query(p,now-1)+query(reflect(p,now),now-1); } int m,n; signed main(){ scanf("%d",&n); for(int re i=1;i<=n;++i){ st[i].x=getdb(); st[i].y=getdb(); ed[i].x=getdb(); ed[i].y=getdb(); } scanf("%d",&m); while(m--){ Point p; p.x=getdb(); p.y=getdb(); printf("%d\n",query(p,n)); } return 0; }