题目描述

给定一张无重边、自环、割点的平面图，你需要回答 Q 次询问，每次询问会给出一个简单环，你需要回答在由这个简单环围成的多边形内部（包括边界上）的点有多少个。
保证图中每条线段不会通过除这条线段端点以外的其他点。

题解

神仙题，和https://www.cnblogs.com/gmh77/p/12103683.html有异曲同工之妙，但是不用转对偶图

新建一个最左下的点和x最小的点连边，按照遍历顺序（bfs）建树

神奇操作：对于环上的每个点，如果其某个儿子在环外则减去儿子的size，如果其父亲在环外则加上自己的size

大概是每次把跑到环外面的那部分减掉

把每个点的连边排序，二分+简单分类讨论

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define inf 2133333333
#define ll long long
#define file
using namespace std;

struct p{
	ll x,y;
	int s,id,sum;
	void js()
	{
		if (!y) {if (x>0) s=1; else s=5;return;}
		if (!x) {if (y>0) s=3; else s=7;return;}
		if (x>0 && y>0) {s=2;return;}
		if (x<0 && y>0) {s=4;return;}
		if (x<0 && y<0) {s=6;return;}
		if (x>0 && y<0) {s=8;return;}
	}
} b[600001],O={0,0},c[100001];
int a[600001][2],ls[100001],bg[100001],ed[100001],d[100001],fa[100001],size[100001],n,m,i,j,k,l,Fa,len,tot,Q,mn,mn2;
ll sum[600001],s,ans;
bool Bz[600001];

void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
ll cj(p a,p b,p c) {return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);}
ll dj(p a,p b,p c) {return (b.x-a.x)*(c.x-a.x)-(b.y-a.y)*(c.y-a.y);}
bool cmp(p a,p b) {return a.s<b.s || a.s==b.s && cj(O,a,b)<0;}
void swap(int &x,int &y) {int z=x;x=y;y=z;}

void bfs()
{
	int d[100011],i,j,k,l,h=0,t=0;
	bool bz[100001];
	
	memset(bz,0,sizeof(bz));d[1]=0;bz[0]=1;h=0;t=1;size[0]=1;
	while (h<t)
	{
		for (i=ls[d[++h]]; i; i=a[i][1])
		if (!bz[a[i][0]])
		{
			Bz[i]=1;
			bz[a[i][0]]=1;
			d[++t]=a[i][0];
			fa[a[i][0]]=d[h];
		}
	}
	fd(i,t,2) ++size[d[i]],size[fa[d[i]]]+=size[d[i]];
}

int find(int t,int t2)
{
	int i,j,k,l=bg[t],r=ed[t],mid;
	p C={c[t2].x-c[t].x,c[t2].y-c[t].y};C.js();
	
	while (l<r)
	{
		mid=(l+r)/2;
		if (b[mid].id==t2) return mid;
		if (cmp(b[mid],C)) l=mid+1; else r=mid;
	}
	return l;
}

int main()
{
	freopen("graph.in","r",stdin);
	#ifdef file
	freopen("graph.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	fo(i,1,m) scanf("%d%d",&j,&k),New(j,k),New(k,j);
	fo(i,1,n) scanf("%lld%lld",&c[i].x,&c[i].y),c[i].id=i;
	mn=inf;c[0]={-inf,-inf};
	fo(i,1,n) if (c[i].x<mn) mn=c[i].x,mn2=i;
	New(0,mn2),New(mn2,0);
	
	bfs();
	fo(i,1,n) {bg[i]=tot+1; for (j=ls[i]; j; j=a[j][1]) {b[++tot]={c[a[j][0]].x-c[i].x,c[a[j][0]].y-c[i].y,0,c[a[j][0]].id},b[tot].js(); if (Bz[j]) b[tot].sum=size[a[j][0]];} ed[i]=tot;}
	fo(i,1,n) if (bg[i]<=ed[i]) sort(b+bg[i],b+ed[i]+1,cmp);
	fo(i,1,n) {sum[bg[i]]=(b[bg[i]].id!=fa[i])*b[bg[i]].sum; fo(j,bg[i]+1,ed[i]) sum[j]=sum[j-1]+(b[j].id!=fa[i])*b[j].sum;}
	
	scanf("%d",&Q);
	for (;Q;--Q)
	{
		scanf("%d",&tot);
		fo(i,1,tot) scanf("%d",&d[i]);
		
		s=0;fo(i,1,tot) s+=cj(O,c[d[i]],c[d[i%tot+1]]);
		if (s>0) fd(i,tot/2,1) swap(d[i],d[tot-i+1]);
		
		ans=0;
		fo(i,1,tot)
		{
			Fa=find(d[i],fa[d[i]]);k=find(d[i],d[i%tot+1]);l=find(d[i],d[(i-2+tot)%tot+1]);
			
			if (k<l)
			{
				if (k>bg[d[i]]) ans-=sum[k-1];ans-=sum[ed[d[i]]]-sum[l];
				if (Fa<k || Fa>l) ans+=size[d[i]];
			}
			else
			{
				ans-=sum[k-1]-sum[l];
				if (Fa>l && Fa<k) ans+=size[d[i]];
			}
		}
		printf("%lld\n",ans);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6681. 【2020.06.02省选模拟】图

原文：https://www.cnblogs.com/gmh77/p/13040061.html