Illuminations

The first line contains two integers $n(3 \le n \le 2 \times 10^5)$ and $m(1 \le m \le 2 \times 10^5)$ .

Each of the following $n$ lines describes a vertex on the convex polygon with two integers x and y $(|x|, |y| \le 10^9)$ , indicating the coordinates of a vertex on the polygon. All these vertices are given in counter-clockwise order and any three of them are not collinear.

Then the following $m$ lines contain m different points outside the polygon describing all legal positions to install illuminants. The i-th line contains two integers $x$ and $y$ $(|x|, |y| \le 10^9)$ , indicating the coordinates of the $i$ -th position. All these positions would not lie in some extension lines for the sides of the polygon.

If it is impossible to light up all exterior boundaries of the polygon, output a single line with a single integer $-1$ .

Otherwise output two lines. Firstly, output a line with a single integer $k$ , representing the least number of illuminants needed to light up all the boundaries. Then, output a line with $k$ space-separated distinct integers, describing a feasible scheme, each of which is the index of a selected position.

All feasible schemes are allowed, so you can output any of them.

C++ 解法, 执行用时: 234ms, 内存消耗: 18476K, 提交时间: 2021-08-17 20:36:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=2e5+5;
struct node{
	int x,y;
    node operator -(const node b)const{
        return (node){x-b.x,y-b.y};
    }
    ll operator *(node b){
        return (ll)x*b.y-(ll)b.x*y;
    }
}p[M],q;
int id[M];
int n,f[20][M];
template <typename F>
int find(F f){
	bool up=f(0,1);
	int l=0,r=n;
	while(l!=r){
		int m=(l+r)/2;
		if(f(0,m)){
			if(up)l=m+1;
			else r=m;
		}else{
			if(f(m,m+1))r=m;
			else l=m+1;
		}
	}
	return l;
}
int main(){
	int m;
	scanf("%d%d",&n,&m); 
	for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);
	reverse(p,p+n);//顺时针方向 
	p[n]=p[0];
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q.x,&q.y);
		int l=find([&](int i,int j){return (p[i]-q)*(p[j]-q)>0;});
		int r=find([&](int i,int j){return (p[i]-q)*(p[j]-q)<0;});
		l%=n,r%=n;
		int len=(r-l+n)%n;
		if(len>f[0][l]){
			f[0][l]=len;
			id[l]=i;
		}
	}
	for(int i=0;i<2*n;i++){
		int len=f[0][i%n]-1;
		if(len>f[0][(i+1)%n]){
			f[0][(i+1)%n]=len;
			id[(i+1)%n]=id[i%n];
		}
	}
	for(int i=0;i<n;i++){
		if(f[0][i])continue;
		puts("-1");
		return 0;
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			f[j][i]=min(f[j-1][i]+f[j-1][(i+f[j-1][i])%n],n);
		}
	}
	int ans=1e9,st=0;
	for(int i=0;i<n;i++){
		int x=i,sum=0,cnt=0;
		for(int j=19;j>=0;j--)
		if(sum+f[j][x]<n){
			sum+=f[j][x];
			x=(x+f[j][x])%n;
			cnt+=1<<j;
		}
		if(cnt+1<ans){
			ans=cnt+1;
			st=i;	
		}
	}
	printf("%d\n",ans);
	while(ans--){
		printf("%d%c",id[st]," \n"[ans==0]);
		st=(st+f[0][st])%n;
	}
	return 0;
}

详情