我們可以先觀察，對於任何一個多邊形，裡面的點和外面的點有甚麼差別？尤其是對邊界的影響
沒錯，從外面的某一點要走到裡面的點要經過奇數次邊界，走到外面的點則是偶數次！
再仔細思考，走到裡面的點進去的次數會比出來的次數多1，走到外面的點則一樣多！
那我們不妨新增一個不管多邊形怎麼給都會在外面的一個點，把這個點連$N$條路徑到每一個點，每當求一個多邊形的答案時，就沿著邊界統計路徑進來多少次、出去多少次，答案就是「進來的次數-出去的次數」
注意考慮的邊應該要是從邊界向外的，否則邊上的點會沒算到
經過同一條邊的路徑可以合併成流量，這樣所有邊的流量可以用一次dfs，$O(N+M)$處理出來
每個點連出去的邊可以先極角排序，再將流量處理成前綴合，這樣沿著邊界統計時每個點的流量才可以$O(1)$算出
至於要統計向外的邊，其實不用執著，只要兩個方向統計出來的答案，取負的那個 (一定有一個$<0$，一個$\geq 0$) 轉正號就好了 (負數的原因是因為流量是向內流進圖形裡面的，而我們統計了向外方向的邊)
時間複雜度：$O(N+M+M\log M+\sum k)$
code:
#include<cstdio> #include<cassert> #include<vector> #include<algorithm> #include<map> using namespace std; typedef long long LL; const LL INF=9223372036854775807LL; struct Point { LL x,y; Point(){} Point(const LL &_x,const LL &_y):x(_x),y(_y){} Point operator-(const Point &a)const{return Point(x-a.x,y-a.y);} int Quantarium()const { if(y>=0LL&&x>0LL)return 1; if(y>0LL&&x<=0LL)return 2; if(y<=0LL&&x<0LL)return 3; if(y<0LL&&x>=0LL)return 4; assert(!(x==0LL&&y==0LL)); assert(0);return -1; } bool operator<(const Point &b)const { const int qa=Quantarium(),qb=b.Quantarium(); if(qa!=qb)return qa<qb; switch(qa) { case 1:return y*b.x<b.y*x;//y/x<b.y/b.x case 2:return y*(-b.x)>b.y*(-x);//y/-x>b.y/-b.x case 3:return (-y)*(-b.x)<(-b.y)*(-x);//-y/-x<-b.y/-b.x case 4:return (-y)*b.x>(-b.y)*x;//-y/x>-b.y/b.x default:assert(0);return true; } } }P[100001]; struct Edge { const int a,b; int flow; Edge():a(),b(){} Edge(const int _a,const int _b,const int _flow):a(_a),b(_b),flow(_flow){} bool operator<(const Edge &e)const { assert(a==e.a); return P[b]-P[a]<P[e.b]-P[a]; } }; vector<Edge>EDGE; vector<int>ET[100001],SUM[100000]; map<int,int>IDX[100000]; int Dfs(const int u,bool *vis) { if(vis[u])return 0; vis[u]=true; int ans=1; for(const int ei:ET[u]) { const Edge &e=EDGE[ei]; const int flow=Dfs(e.b,vis); ans+=flow; EDGE[ei].flow+=flow,EDGE[ei^1].flow-=flow; } return ans; } int N,M; void CreateFlow() { static bool vis[100001]; for(int i=0;i<=N;i++)vis[i]=false; assert(Dfs(N,vis)==N+1); } void AddEdge(const int a,const int b) { const int sz=EDGE.size(); EDGE.push_back(Edge(a,b,0)); ET[a].push_back(sz); } int GetSum(const int a,const int o,const int b,const bool type) { const vector<int>&sum=SUM[o]; const auto ita=IDX[o].find(a),itb=IDX[o].find(b); assert(ita!=IDX[o].end()&&itb!=IDX[o].end()); const int ia=(type?itb:ita)->second; const int ib=(type?ita:itb)->second; assert(ia!=ib); if(ia<ib)return sum[ib-1]-sum[ia]; else return sum[(int)sum.size()-1]-(sum[ia]-(ib?sum[ib-1]:0)); } bool CmpEdgeIdx(const int a,const int b){if(a==b)return false;return EDGE[a]<EDGE[b];} int main() { // freopen("in.txt","r",stdin); while(scanf("%d%d",&N,&M)==2) { for(int i=0;i<=N;i++)ET[i].clear(); EDGE.clear(); for(int i=0,a,b;i<M;i++) { scanf("%d%d",&a,&b),a--,b--; AddEdge(a,b),AddEdge(b,a); } for(int i=0;i<N;i++)scanf("%I64d%I64d",&P[i].x,&P[i].y); if(true) { LL mn=INF; int left=-1; for(int i=0;i<N;i++)if(P[i].x<mn)mn=P[i].x,left=i; assert(left!=-1); AddEdge(left,N),AddEdge(N,left); P[N].x=-1e9-1,P[N].y=P[left].y; } CreateFlow(); for(int i=0;i<N;i++) { sort(ET[i].begin(),ET[i].end(),CmpEdgeIdx); IDX[i].clear(); for(int j=0;j<(int)ET[i].size();j++)IDX[i][EDGE[ET[i][j]].b]=j; SUM[i].clear(); int sum=0; for(const int ei:ET[i])SUM[i].push_back(sum+=EDGE[ei].flow); assert(IDX[i].size()==ET[i].size()&&SUM[i].size()==ET[i].size()); } int querycount;scanf("%d",&querycount); for(int k;querycount--;) { scanf("%d",&k); vector<int>a; for(int i=0,v;i<k;i++)scanf("%d",&v),a.push_back(--v); assert(k==(int)a.size()&&k>=3); int ans1=0,ans2=0; for(int i=0;i<k;i++) { ans1+=GetSum(a[i],a[(i+1)%k],a[(i+2)%k],false); ans2+=GetSum(a[i],a[(i+1)%k],a[(i+2)%k],true); } printf("%d\n",-min(ans1,ans2)); } } return 0; }
沒有留言:
張貼留言
歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。