Description
- 给定一张无重边、自环、割点的平面图，你需要回答 Q 次询问，每次询问会给出一个简单环，你需要回答在由这个简单环围成的多边形内部（包括边界上）的点有多少个。
- 保证图中每条线段不会通过除这条线段端点以外的其他点。
- 询问按照顺时针或逆时针给出。
n<=1e5,m<=3e5
source:CF223E
Solution
- 由于这是一个平面图，什么特殊的样子都没有，非常的优美，所以也有一个优美的结论：
- 任意造一个生成树，树根为汇点，每一个点有1点初始流量流向它的父亲（有向边），每条边有sz[x]的流量流过。
- 一个多边形内的点数就是所有边界上的点，入边不在多边形内的流量，与出边不在多边形内的流量之差。
- 感性理解，非常正确，一些边进来，又流出去，多出的流量就是这个多边形内新产生的，即点数。
- 那么只需要极角排序加二分前缀和就可以算出不在多边形内的入边（这显然是一个区间）的流量之和了。
- PS：判顺时针逆时针用叉积算面积。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 300005
#define ll long long
#define db double
using namespace std;
const db Pi=acos(-1.0);
int n,m,i,j,k,Q,q[maxn];
struct dot{
int x,y;
dot(int _x=0,int _y=0){x=_x,y=_y;}
} p[maxn];
dot operator-(dot a,dot b){return dot(a.x-b.x,a.y-b.y);}
ll operator*(dot a,dot b){return (ll)a.x*b.y-(ll)a.y*b.x;}
struct vec{
dot x; int id; db r;
vec(dot _x=0,int _id=0){x=_x,id=_id,r=atan2(x.y,x.x);r+=(r<0)?2*Pi:0;}
};
vector<vec> E[maxn],e[maxn];
vector<ll> s[maxn];
int cmp(vec a,vec b){return a.r<b.r;}
void read(int &x){
x=0; char ch=getchar(); int tp=1;
for(;(ch<'0'||ch>'9')&&(ch!='-');ch=getchar());
if (ch=='-') tp=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
x=x*tp;
}
int bz[maxn],sz[maxn],fa[maxn],d[maxn];
void BFS(int st){
int t=0,w=1; d[1]=st,bz[st]=1;
while (t<w){
int x=d[++t];
for(int i=0;i<E[x].size();i++) if (!bz[E[x][i].id]){
e[x].push_back(E[x][i]),bz[E[x][i].id]=1;
fa[E[x][i].id]=x,d[++w]=E[x][i].id;
}
}
for(i=w;i>=1;i--) sz[d[i]]++,sz[fa[d[i]]]+=sz[d[i]];
}
int main(){
read(n),read(m);
for(i=1;i<=m;i++) {
read(j),read(k);
E[j].push_back(vec(0,k));
E[k].push_back(vec(0,j));
}
for(i=1;i<=n;i++) read(p[i].x),read(p[i].y);
for(i=1;i<=n;i++){
for(j=0;j<E[i].size();j++)
E[i][j]=vec(p[E[i][j].id]-p[i],E[i][j].id);
sort(E[i].begin(),E[i].end(),cmp);
}
p[0]=dot(-1e9-1,-1e9-1);
int id=1; for(i=2;i<=n;i++) if (p[i].x<p[id].x) id=i;
BFS(id);
for(i=1;i<=n;i++){
s[i].push_back(0);
for(j=0;j<e[i].size();j++)
s[i].push_back(s[i][s[i].size()-1]+sz[e[i][j].id]);
}
read(Q); int K; ll sq,ans;
while (Q--){
read(K);for(i=1;i<=K;i++) read(q[i]);
for(sq=0,i=1;i<=K;i++) sq+=p[q[i]]*p[q[i%K+1]];
if (sq<0) for(i=1;i<=K/2;i++) swap(q[i],q[K-i+1]);
ans=0;
for(i=1;i<=K;i++){
int x=q[i],nex=q[i%K+1],pre=q[(i-1+K-1)%K+1];
dot v1=p[nex]-p[x],v2=p[pre]-p[x];
db r1=atan2(v1.y,v1.x),r2=atan2(v2.y,v2.x);
dot v3=p[fa[x]]-p[x]; db r3=atan2(v3.y,v3.x);
if (r1<0) r1+=2*Pi; if (r2<0) r2+=2*Pi; if (r3<0) r3+=2*Pi;
if (r2<r1) { if (r2<r3&&r3<r1) ans+=sz[x]; } else
if (r3>r2||r3<r1) ans+=sz[x];
int l=0,r=e[x].size()-1,mid,id1=-1,id2=-1;
while (l<=r){
int mid=(l+r)>>1;
if (e[x][mid].r<r1) id1=mid,l=mid+1;
else r=mid-1;
}
l=0,r=e[x].size()-1;
while (l<=r){
int mid=(l+r)>>1;
if (e[x][mid].r<=r2) id2=mid,l=mid+1;
else r=mid-1;
}
if (r2<r1) ans-=s[x][id1+1]-s[x][id2+1]; else
ans-=s[x][id1+1]+s[x][s[x].size()-1]-s[x][id2+1];
}
printf("%lld
",ans);
}
}