題意： 給你一堆坐標點，然後告訴你他們之間的連接情況，所有的邊都是雙向的，並且圖是連通的。邊數，點數都是10w級別
然後開始詢問，每個詢問是輸入圖中某個多邊形的所有頂點，然後問你這個多邊形內部一共有幾個點（包括邊界上的點）
看完後就懂了，關鍵就是利用流的思想，當選定某個簡單多邊形的時候，內部的點數就等於流進去的流量和減去流出來的流量和，反正就是流量差，怎麼定義很自由
統計的時候不能暴力
利用坐標的極角序處理出一個前綴和就可以很快得到答案
具體見代碼
關於多邊形的內部究竟在哪一側還是搞了我很長時間，太糾結了
[cpp]
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define MP make_pair
#define PB push_back
const int maxn = 100010;
const double inf = 1e10;
struct Point {
double x,y;
Point(){};
Point(double sx,double sy) : x(sx),y(sy){}
}p[maxn];
double operator / (const Point &b,const Point &a) {
return atan2(b.y-a.y,b.x-a.x);
}
bool operator < (const Point &a,const Point &b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
inline double cross(double x1,double y1,double x2,double y2){
return x1*y2-x2*y1;
}
inline double chacha(Point s,Point a,Point b){
return cross(a.x-s.x,a.y-s.y,b.x-s.x,b.y-s.y);
}
struct Edge{
double ang;
int to;
Edge(){}
Edge(double a,int t):ang(a),to(t){};
bool operator < (const Edge &cmp) const{
return ang<cmp.ang;
}
};
vector<Edge> edge[maxn];
map<pair<int,int>,int> sum,flow;
int all[maxn];
int n,m;
inline void add_edge(int u,int v)
{
Edge k;
k.to=v;k.ang=p[v]/p[u];
edge[u].PB(k);
flow[MP(u,v)]=0;
}
bool vis[maxn];
int dfs(int u,int f)
{
vis[u]=true;
int cnt=1;
for(vector<Edge>::iterator it=edge[u].begin();it!=edge[u].end();it++)
{
int v=it->to;
if(!vis[v]) cnt+=dfs(v,u);
}
if(f)
{
flow[MP(f,u)]+=cnt;
flow[MP(u,f)]-=cnt;
}
return cnt;
}
int ss[maxn],tt[maxn];
vector<int> cut;
inline int gao(int a,int b,int c)
{
double bb = p[b]/p[a],cc = p[c]/p[a];
if(bb < cc)
{
return sum[MP(a,c)] - sum[MP(a,b)] - flow[MP(a,c)];
}
else
{
return all[a] + sum[MP(a,c)] - sum[MP(a,b)] - flow[MP(a,c)];
}
}
void solve()
{
int ans=0,num=cut.size(),i;
double s=0;p[0]=Point(0,0);
for(i=0;i<num;i++)
s+=chacha(p[0],p[cut[i==0 ? num-1 : i-1]],p[cut[i]]);
if(s>0) reverse(cut.begin(),cut.end());//變成順時針
for(i=0;i<num;i++)
{
int tmp=gao( cut[i], cut[(i==0 ? num-1 : i-1)] , cut[(i+1)%num] ) ;
ans+=tmp;
}
printf("%d\n",ans+num);
}
int main()
{
int u,v,q,k,i,j,leftmost,T,cir,c;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) scanf("%d%d",&ss[i],&tt[i]);
for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
for(i=1;i<=m;i++)
{
add_edge(ss[i],tt[i]);
add_edge(tt[i],ss[i]);
}
p[T=n+1]=Point(-inf,0);
for(leftmost=i=1;i<=n;i++)
if(p[i]<p[leftmost]) leftmost=i;
add_edge(T,leftmost);
add_edge(leftmost,T);
dfs(T,0);
for(i=1;i<=n+1;i++) sort(edge[i].begin(),edge[i].end());
for(i=1;i<=n+1;i++)
{
int pre=i;
sum[MP(i,i)] = 0;
for(vector<Edge>::iterator it=edge[i].begin();it!=edge[i].end();it++)
{
all[i]+=flow[MP(i,it->to)];
sum[MP(i,it->to)] = sum[MP(i,pre)] + flow[MP(i,it->to)];
pre=it->to;
}
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&k);cut.clear();
for(i=1;i<=k;i++) scanf("%d",&c),cut.PB(c);
solve();
}
return 0;
}
