Rikka with Illuminations ICPC 2018 Xuzhou R

[ICPC 2018 Xuzhou R] Rikka with Illuminations

计算几何好难 /kel

题目链接： [ICPC 2018 Xuzhou R] Rikka with Illuminations 。

题目描述：

有 nn 个点的凸包和 mm 个光源。求最少多少个光源可以覆盖凸包的所有边。要求构造方案。

n,m≤103n,m\le 10^3 。

首先要做一步转化。注意到图形是凸包，所以每一个光源覆盖的区域实际上是一个凸包的边的连续区间。

所以问题变为：

  • 如何计算每一个光源的覆盖区间。
  • 环形最小区间覆盖问题。

Part I.

考虑计算一个边被一个光源覆盖的充要条件。

经过手动模拟和注意力后我们得出结论：当凸包的点逆时针排序后，一个边向量 AA 被光源 pp 照亮当且仅当 pp 在 AA 的右边。

所以就解决了。

注意由于是环，所以我们应该记录起点和长度，而非起点和终点。

像这样：

1
2
3
4
5
6
7
8
9
10
11
for(int i=0;i<m;i++){
    st[i]=len[i]=0;
    for(int j=0;j<n;j++)vis[j]=(cross(p[(j+1)%n]-p[j],q[i]-p[j])<0),len[i]+=vis[j];
    for(int j=0;j<n;j++){
        int t=(j==0?n-1:j-1);
        if(vis[j]&&!vis[t]){
            st[i]=j;
            break;
        }
    }
}

Part II.

经典贪心问题，只不过是环所以处理较为麻烦。

首先我们应该断环为链，即枚举一个断点断开，将所有边摊开为 [0,2n)[0,2n) 中的点。

然后对于每一次断边，我们应该首先计算原来的区间映射到新区间的结果。

接着直接贪心就行。注意当覆盖的边的编号 ≥n\ge n 是直接结束，因为此时已经覆盖完全了。

像这样：

1
2
3
4
5
6
7
8
9
10
for(int i=0,j=0;i<n;){
	int maxn=-1,id=0;
	while(j<m&&v[j].s<=i){
		if(maxn<v[j].t)maxn=v[j].t,id=v[j].id;
		j++;
	}
	if(!~maxn)return vector<int>(m+1,0);
	ans.push_back(id);
	while(i<n&&i<=maxn)i++;
}

于是就做完了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
using ll=long long;
int T,n,m,st[N],len[N],vis[N];
struct point{
    ll x,y;
    point(){x=y=0;}
    point(ll x,ll y):x(x),y(y){}
    point operator-(point a){return point(x-a.x,y-a.y);}
};
ll cross(point a,point b){return a.x*b.y-a.y*b.x;}
vector<point>p,q;
vector<int>Min(vector<int>a,vector<int>b){
	return a.size()<=b.size()?a:b;
}
struct node{
	int s,t,id;
};
bool operator<(node x,node y){
	return x.s==y.s?x.t<y.t:x.s<y.s;
}
vector<int>calc(int x){
	vector<node>v;
	vector<int>ans;
	for(int i=0;i<m;i++){
		int s=st[i]-x+1,t=st[i]+len[i]-x;
		while(s<0)s+=n,t+=n;
		v.push_back({s,t,i});
	}
	sort(v.begin(),v.end());
	for(int i=0,j=0;i<n;){
		int maxn=-1,id=0;
		while(j<m&&v[j].s<=i){
			if(maxn<v[j].t)maxn=v[j].t,id=v[j].id;
			j++;
		}
		if(!~maxn)return vector<int>(m+1,0);
		ans.push_back(id);
		while(i<n&&i<=maxn)i++;
	}
	return ans;
}
void WZH(){
    scanf("%d%d",&n,&m);
    p.resize(n),q.resize(m);
    for(int i=0,x,y;i<n;i++)scanf("%d%d",&x,&y),p[i]=point(x,y);
    for(int i=0,x,y;i<m;i++)scanf("%d%d",&x,&y),q[i]=point(x,y);
    if(m==0)return (void)(puts("-1"));
    for(int i=0;i<m;i++){
        st[i]=len[i]=0;
        for(int j=0;j<n;j++)vis[j]=(cross(p[(j+1)%n]-p[j],q[i]-p[j])<0),len[i]+=vis[j];
        for(int j=0;j<n;j++){
            int t=(j==0?n-1:j-1);
            if(vis[j]&&!vis[t]){
                st[i]=j;
                break;
            }
        }
    }
    vector<int>ans(m+1,0);
    for(int i=0;i<n;i++)ans=Min(ans,calc(i));
    if(ans.size()==m+1)return (void)(puts("-1"));
    printf("%zu\n",ans.size());
    for(int u:ans)printf("%d ",u+1);puts("");
}
int main(){
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}