听了遍dls的讲解觉得这是个沙比题，结果调了两个小时。。。
主要注意的点有两个，
一个是 找每个灯覆盖的区间，这个用叉积看一下夹角即可
一个是 覆盖的时候点覆盖比边覆盖好写(个人感觉)
点覆盖的话，如果当前光源能照到[l,r]的点，那下一次直接找<=r的就可以了，最后判断覆盖n个点
边的话,如果是[l,r]的边，那么下一次就要找<=r+1的，最后判断覆盖n-1条边。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 typedef double db; 8 const int N = 2005; 9 const db eps = 1e-6; 10 const db pi = acos(-1); 11 int sign(db k){ 12 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 13 } 14 int cmp(db k1,db k2){return sign(k1-k2);} 15 struct point{ 16 db x,y; 17 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 18 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 19 point operator * (db k1) const{return (point){x*k1,y*k1};} 20 point operator / (db k1) const{return (point){x/k1,y/k1};} 21 int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;} 22 }; 23 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;} 24 db dot(point k1,point k2){return k1.x*k2.y-k1.y+k2.x;} 25 int t,n,m; 26 point p[N],s[N]; 27 struct O{ 28 int s,t,inx; 29 bool operator <(const O &o)const{ 30 if(s==o.s)return t>o.t; 31 else return s<o.s; 32 } 33 }; 34 vector<O>v; 35 vector<int> ans,tmp; 36 void slove(){ 37 for(int l=0;l<v.size();l++){ 38 tmp.clear(); 39 int cur=l; 40 tmp.push_back(v[cur].inx); 41 while (v[cur].t<v[l].s+n){ 42 int mx = v[cur].t; 43 for(int r=l+1;r<v.size()&&v[r].s<=mx;r++){ 44 if(v[r].t>v[cur].t) cur=r; 45 } 46 if(v[cur].t==mx)break; 47 tmp.push_back(v[cur].inx); 48 } 49 if(v[cur].t>=v[l].s+n&&(ans.empty()||tmp.size()<ans.size())) 50 ans=tmp; 51 } 52 } 53 int main(){ 54 scanf("%d",&t); 55 while(t--){ 56 v.clear();ans.clear(); 57 scanf("%d%d",&n,&m); 58 for(int i=0;i<n;i++){// 59 scanf("%lf%lf",&p[i].x,&p[i].y); 60 p[i+n]=p[i]; 61 } 62 for(int i=0;i<m;i++){ 63 scanf("%lf%lf",&s[i].x,&s[i].y); 64 } 65 for(int i=0;i<m;i++){ 66 int l=0,r; 67 for(int j=0;j<n;j++){ 68 if(cross(p[j+1]-p[j],p[j]-s[i])>0&&cross(p[j]-p[j-1+n],p[j-1+n]-s[i])<=0) 69 l=j; 70 } 71 r=l; 72 while (r<=l+n){ 73 if(cross(p[r+1]-p[r],p[r]-s[i])>0)r++; 74 else break; 75 } 76 v.push_back({l,r,i+1});//点覆盖 77 //if(r+n<2*n)v.push_back({l+n,r+n,i+1}); 78 } 79 sort(v.begin(),v.end()); 80 slove(); 81 if(ans.empty()) 82 printf("-1 "); 83 else { 84 printf("%d ", ans.size()); 85 for (int i = 0; i < ans.size(); i++) { 86 printf("%d%c", ans[i], i == ans.size() - 1 ? ' ' : ' '); 87 } 88 } 89 } 90 } 91 /** 92 1 93 3 1 94 0 0 95 1 0 96 0 1 97 -1 -1 98 */