An n-gon is a polygon with n sides. For example, a triangle is a 3-gon. Now you are asked to find the best n-gon in a given convex N-gon. The vertices of the n-gon are selected from vertices of the N-gon. The n-gon you are supposed to find must have the largest area among all possible n-gons, which means that it approximates the N-gon the best. The figure below shows the best 6-gon (the shaded part) in a 10-gon.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N ( 6 ) which is the total number of vertices of the convex N-gon, and n ( 6 ) which is the total number of vertices of the approximating convex n-gon. Then N lines follow, the i-th line gives the 2-D coordinates (x, y) of the i-th vertex ( , ). The x and y coordinates in a line are real numbers with their absolute values no more than 1000, and they are separated by a space.
Output Specification:
Print in a line all the vertex indices of the best n-gon in descending order. All the numbers are separated by a space and there must be no extra space at the beginning or the end of the line. It is guaranteed that the solution is unique.
Sample Input:
10 6
133.0 1.0
544.0 71.0
558.0 206.0
536.0 338.0
463.0 436.0
330.0 503.0
188.0 499.0
305.0 2.0
55.0 410.0
2.0 140.0
Sample Output:
9 8 5 3 1 01 #include<bits/stdc++.h> 2 using namespace std; 3 double x,y; 4 int n,m; 5 const double eps=1e-8; 6 inline int sgn(double d) 7 {return d<-eps?-1:d>eps;} 8 struct point 9 { 10 double x; 11 double y; 12 int id; 13 } po; 14 struct cmp1 15 { 16 bool operator() (const point& p1,const point& p2) const 17 { 18 return atan2((p1.y-y),(p1.x-x))<atan2((p2.y-y),(p2.x-x)); 19 } 20 }; 21 vector<point> v; 22 vector<double> va; 23 inline double area(int n1,int n2) 24 { 25 if(!sgn(va[n1*n+n2])) 26 { 27 va[n1*n+n2]=v[n1].x*v[n2].y-v[n1].y*v[n2].x; 28 va[n2*n+n1]=-va[n1*n+n2]; 29 } 30 return va[n1*n+n2]; 31 } 32 int main() 33 { 34 // freopen("data1.txt","r",stdin); 35 scanf("%d %d",&n,&m); 36 va.resize(n*n,0.0); 37 x=0.0; 38 y=0.0; 39 for(int i=0;i<n;i++) 40 { 41 scanf("%lf %lf",&po.x,&po.y); 42 x+=po.x; 43 y+=po.y; 44 po.id=i; 45 v.emplace_back(po); 46 } 47 x=x/n; 48 y=y/n; 49 sort(v.begin(),v.end(),cmp1()); 50 vector<pair<double,int> > vdp((n-2)*(n-2)*(m-2),make_pair(0.0,0)); 51 for(int i=0;i<n-2;i++) 52 { 53 for(int j=i+2;j<n;j++) 54 { 55 double maxs=0.0; 56 int k=i+1; 57 for(;k<j;) 58 { 59 double s=area(i,k)+area(k,j)+area(j,i); 60 if(sgn(s-maxs)>0) 61 { 62 k++; 63 maxs=s; 64 } 65 else 66 break; 67 } 68 vdp[i*(n-2)+j-2].first=maxs; 69 if(k<j) 70 vdp[i*(n-2)+j-2].second=k-1; 71 else 72 vdp[i*(n-2)+j-2].second=j-1; 73 } 74 } 75 for(int l=1;l<m-2;l++) 76 { 77 for(int i=0;i<n-l-2;i++) 78 { 79 double maxs=0.0; 80 int kk=0; 81 for(int j=i+l+2;j<n;j++) 82 { 83 for(int jj=i+l+1;jj<j;jj++) 84 if(sgn(maxs-vdp[(l-1)*(n-2)*(n-2)+i*(n-2)+jj-2].first-area(jj,j)-area(j,i)-area(i,jj))<0) 85 { 86 maxs=vdp[(l-1)*(n-2)*(n-2)+i*(n-2)+jj-2].first+area(jj,j)+area(j,i)+area(i,jj); 87 kk=jj; 88 } 89 vdp[l*(n-2)*(n-2)+i*(n-2)+j-2].first=maxs; 90 vdp[l*(n-2)*(n-2)+i*(n-2)+j-2].second=kk; 91 } 92 } 93 } 94 double maxs=0.0; 95 int ii=0,jj=0; 96 for(int i=0;i<(n-m+1);i++) 97 { 98 for(int j=i+m-3;j<n-2;j++) 99 { 100 if(sgn(maxs-vdp[(m-3)*(n-2)*(n-2)+i*(n-2)+j].first)<0) 101 { 102 maxs=vdp[(m-3)*(n-2)*(n-2)+i*(n-2)+j].first; 103 ii=i; 104 jj=j; 105 } 106 } 107 } 108 vector<int> vr; 109 vr.emplace_back(v[ii].id); 110 vr.emplace_back(v[jj+2].id); 111 for(int i=m-3;i>=0;i--) 112 { 113 vr.emplace_back(v[vdp[i*(n-2)*(n-2)+ii*(n-2)+jj].second].id); 114 jj=vdp[i*(n-2)*(n-2)+ii*(n-2)+jj].second-2; 115 } 116 sort(vr.begin(),vr.end(),greater<int>()); 117 printf("%d",vr[0]); 118 for(int i=1;i<m;i++) 119 printf(" %d",vr[i]); 120 return 0; 121 }