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 }