https://codeforc.es/gym/102012/problem/M
我太难了！写了个垃圾代码wa了三天一直过不去最后代码又长又丑果断放弃。。。
题意
n个点，m个灯，问最少用多少个灯可以照亮全部点。
题解
显然贪心。
处理出每个灯的覆盖范围，贪心搞出保证覆盖当前点j的同时能往后覆盖的最大距离add[j]，
最后枚举以每个点为起点的所需灯数，取最少情况输出即可。
1 #define bug(x) cout<<#x<<" is "<<x<<endl
2 #define IO std::ios::sync_with_stdio(0)
3 #define ull unsigned long long
4 #include <bits/stdc++.h>
5 #define iter ::iterator
6 #define pa pair<int,ll>
7 #define pp pair<int,pa>
8 using namespace std;
9 #define ll long long
10 #define mk make_pair
11 #define pb push_back
12 #define se second
13 #define fi first
14 #define ls o<<1
15 #define rs o<<1|1
16 const int N=1e5+5;
17 ll mod=998244353;
18 struct Point{
19 int x,y;
20 };
21 Point operator -(Point A,Point B){
22 return (Point){A.x-B.x,A.y-B.y};
23 }
24 ll Cross(Point A,Point B){
25 return (1ll*A.x*B.y-1ll*A.y*B.x);
26 }
27 Point p[N],t[N];
28 int add[N],id[N];
29 int T,n,m;
30 int main(){
31 scanf("%d",&T);
32 while(T--){
33 scanf("%d%d",&n,&m);
34 for(int i=0;i<n+m;i++){
35 add[i]=id[i]=0;
36 }
37 for(int i=0;i<n;i++){
38 scanf("%d%d",&p[i].x,&p[i].y);
39 }
40 for(int i=0;i<m;i++){
41 scanf("%d%d",&t[i].x,&t[i].y);
42 }
43 for(int i=0;i<m;i++){
44 int l=0,r=0;
45 for(int j=1;j<n;j++){
46 if(Cross(p[j]-t[i],p[l]-t[i])<0)l=j;
47 if(Cross(p[j]-t[i],p[r]-t[i])>0)r=j;
48 }
49 for(int j=l;j!=r;j=(j+1)%n){
50 j%=n;
51 if(add[j]<(r-j+n)%n)add[j]=(r-j+n)%n,id[j]=i;
52 }
53 }
54 int f=0;
55 for(int i=0;i<n;i++){
56 if(!add[i]){
57 f=1;
58 break;
59 }
60 }
61 if(f){
62 printf("-1\n");
63 continue;
64 }
65 int ans=1e9,start=0;
66 for(int i=0;i<n;i++){
67 int cnt=0;
68 int j=i;
69 while(j<i+n){
70 j+=add[j%n];
71 cnt++;
72 }
73 if(cnt<ans){
74 ans=cnt;
75 start=i;
76 }
77 }
78 printf("%d\n",ans);
79 int i=start;
80 while(ans--){
81 printf("%d%c",id[i]+1,ans==0?'\n':' ');
82 i+=add[i]%n;
83 }
84 }
85 }