本文共 3618 字，大约阅读时间需要 12 分钟。

题解里有讲先进行排序再插入平衡树

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define youhua __attribute__((optimize("O2")))using namespace std;char c;bool flag;youhua inline void read(int &a){a=0;do c=getchar();while(c!='-'&&(c<'0'||c>'9'));if(c=='-')c=getchar(),flag=true;while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();if(flag)a=-a,flag=false;}youhua inline void read(long long&a){a=0;do c=getchar();while(c!='-'&&(c<'0'||c>'9'));if(c=='-')c=getchar(),flag=true;while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();if(flag)a=-a,flag=false;}struct P{ int x,y;};P Std;youhua inline P operator -(P a,P b){ return (P){a.x-b.x,a.y-b.y};}youhua inline int operator *(P a,P b){ return a.x*b.y-a.y*b.x;}youhua inline bool operator <(P a,P b){ return atan2(a.y-Std.y,a.x-Std.x)
         
          (P a,P b){ return atan2(a.y-Std.y,a.x-Std.x)>atan2(b.y-Std.y,b.x-Std.x);}struct Node{Node *lc,*rc,*f;int rank,size;double Key;youhua inline bool l(){ return f->lc==this;}}*Empty;Node *Stack[100001],Ch[100001];int Tot;youhua inline Node *New(){Node *A=Stack[Tot--];A->size=1,A->rank=1,A->lc=A->rc=Empty;A->f=A;return A;}youhua inline void Del(Node*A){Stack[++Tot]=A;}youhua inline void Bg(){Empty=new Node;Empty->lc=Empty->rc=Empty->f=Empty;Empty->rank=Empty->size=0;for(Tot=0;Tot<=100000;Tot++)Stack[Tot]=Ch+Tot;Tot=100000;}int Cnt;youhua inline void updata(Node *a){Cnt++;a->size=a->lc->size+a->rc->size+1,a->rank=a->lc->size+1;}youhua inline void Lc(Node *a){ Node *f; if(a->f->f==a->f)f=a; else if(a->f->l())f=a->f->f,f->lc=a; else f=a->f->f,f->rc=a; a->f->f=a; a->f->lc=a->rc; a->rc->f=a->f; a->rc=a->f; a->f=f; updata(a->rc);}youhua inline void Rc(Node *a){ Node *f; if(a->f->f==a->f)f=a; else if(a->f->l())f=a->f->f,f->lc=a; else f=a->f->f,f->rc=a; a->f->f=a; a->f->rc=a->lc; a->lc->f=a->f; a->lc=a->f; a->f=f; updata(a->lc);}youhua inline void On(Node *a){a->l()?Lc(a):Rc(a);}youhua inline void Twi(Node *a){a->l()==a->f->l()?On(a->f):On(a);On(a);}youhua void Splay(Node *a){ while(a->f->f!=a->f)Twi(a);while(a->f!=a)On(a);updata(a);}int tmprank;youhua void Insert(Node *Cur,Node *C){ if(C->Key
          
           Key) if(Cur->lc==Empty) {Cur->lc=C,C->f=Cur;updata(C);} else Insert(Cur->lc,C); else if(Cur->rc==Empty) {tmprank+=Cur->rank,Cur->rc=C,C->f=Cur;updata(C);} else tmprank+=Cur->rank,Insert(Cur->rc,C); updata(Cur);}Node *A[100001];P AA[2000];int AAA[2000];youhua inline bool cmp(int a,int b){ return AA[a]>AA[b];}int n,m;int no[2000];int f[2001][2001];int non[2000];youhua void Dele(Node *A){if(A==Empty)return ;Dele(A->lc),Dele(A->rc),Del(A);}youhua inline void Pre(){ Std=(P){-10007,-10009}; for(int i=1;i<=n;i++)no[i]=i; sort(no+1,no+1+n,cmp); for(int i=1;i<=n;i++)non[no[i]]=i; for(int i=1;i
           
            f=A[i]; A[i]->Key=atan2(AA[no[i+1]].y-Std.y,AA[no[i+1]].x-Std.x); updata(A[i]); for(int j=i+2;j<=n;j++) { tmprank=0; Node *AAA=New(); AAA->Key=atan2(AA[no[j]].y-Std.y,AA[no[j]].x-Std.x); Insert(A[i],AAA); if(rand()&5==5) A[i]=AAA,Splay(AAA); f[i][j]=f[j][i]=tmprank; } Dele(A[i]); }}int Cache[2001];youhua inline void getans(){ int s;read(s); for(int i=1;i<=s;i++)read(Cache[i]),Cache[i]++; Cache[s+1]=Cache[1]; int sum=0,tp=0;// sum=f[non[Cache[1]]][non[Cache[2]]]; Std=(P){-10007,-10009}; for(int i=1;i<=s;i++) { if((AA[Cache[i]]-Std)*(AA[Cache[i+1]]-Std)<0) sum-=f[non[Cache[i]]][non[Cache[i+1]]],tp++; else sum+=f[non[Cache[i]]][non[Cache[i+1]]]; } if(sum<0)sum=-sum,tp=s-tp; int ans=sum-tp+1; if(ans<=0) puts("Miss!"); else printf("%d\n",ans);}int main(){ Bg(); read(n); for(int i=1;i<=n;i++)read(AA[i].x),read(AA[i].y); Pre(); read(m); while(m--)getans(); return 0;}