POLYGON(动态规划)

学校老师布置的一道动规的题目，要求下次上课前AC。周一一放学就回家写，调试了一会儿OK了。在这边记录一下解题的思路和过程，也作为第一篇随笔，就是随便之一写，您也就随便之一看。有问题望你指出，多多包涵。

题目描述如下：

POLYGON

源程序名 POLYGON.??? (PAS,C,CPP)

可执行文件名 POLYGON.EXE

输入文件名 POLYGON.IN

输出文件名 POLYGON.OUT

对于一个多边形来说，在该多边形内任取两点，如果这两点连成的线段落在多边形内，则称这样的多边形为凸多边形。

平面上有N个坐标值为自然数的圆点。顶点数最多凸多边形是指由给定的圆点中的一部分组成的凸多边形，它包含最大可能的顶点数。原点，即坐标内中心(0，0)必须是顶点数最多凸多边形的一个顶点。

编写程序求出这样的凸多边形的最大顶点数。注意一个多边形的连续的边不能是平行的。

输入

输入文件的第一行包含一个自然数N，2≤N≤100，表示给定的圆点数。

下面的N行每行包含两个用空格隔开的自然数X和Y，1≤X≤100，1≤Y≤100，表示一个圆点的坐标值。所有的圆点是不相同的。

输出

输出文件的第一行也是唯一的一行应该包含顶点数最多凸多边形的顶点数。注意结果应不小于3。

样例

POLYGON.IN

10 8

3 9

2 8

2 3

9 2

9 10

10 3

8 10

POLYGON.OUT

因为接触信息竞赛时间不长，老师对这道题给了两点提示：

第一点大家在下面也都想到了就是按照斜率给点进行排序再处理；

第二点就是关于判断凸多边形的问题，这里用到了向量和矩阵的知识。这里我们不妨假设斜率是按照从小到大的顺序排列。所以判断(x3,y3)就是否可以和已经构成一边的(x1,y1)、(x2,y2)构成凸多边形。（作者数学不是很好，所以推理不是很严谨）即把(x1,y1)、(x2,y2)构成的一边看作以(x1,y1)为起点，(x2,y2)为终点的向量，而点(x3,y3)就是向量外一点，如果这个向量及其延长线逆时针转一个小于180°的角可以碰到(x3,y3)则判定可以加入这个点，然后用行列式求坐标系中三角形的公式就可以得出如果x1(y2-y3)+x2(y3-y1)+x3(y1-y2)>0 则符合条件(也排除了等于0是三点共线的情况)。

最后老师在黑板上随便写下了一个动态转移方程 Fi=max{Fj+1}.

也就是这个公式是我们走了不少弯路。

因为这是一个点到另一个点的动规情况，并不是一个维度就可以描述出来的。所以我想可以这样写方程

第 i 个点到 i 后第 j 个点可以加入构成凸多边形的最多的变数为Fij ，则 Fij=max{ Fki ，1<=k<=i-1}+1 并且j 如果到了最后一个点之后就返回第一个点，这样在最后扫描一边 Fi1 就可以得到结果了。

具体不是很规范的代码如下：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 FILE *fin,*fout;
 4 int n,f[102][102],max=0,ans=3,y[102], x[102];
 5 double a[102];
 6 void qs(double a[],int x[],int y[],int left,int right){
 7     if(left>=right) return ;
 8     int i=left;
 9     int j=right;
10     double key=a[left];
11     int key2=x[left],key3=y[left];
12      while(i < j)                              
13     {
14         while(i < j && key <= a[j]) j--;
15           { a[i] = a[j]; x[i]=x[j];y[i]=y[j];} 
16         while(i < j && key >= a[i]) i++; 
17            {a[j] = a[i]; x[j]=x[i]; y[j]=y[i];}
18     }
19     a[i] = key;x[i]=key2;y[i]=key3;
20     qs(a,x,y,left,i-1);
21     qs(a,x,y,i+1,right);
22 }
23 int judge(int x1,int y1,int x2,int y2,int x3,int y3){
24     if((x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))>0) return 1;
25     else return 0;
26 } 
27 int main(){
28     int i,j,t,k;
29     fin=fopen("polygon.in","r");
30     fout=fopen("polygon.out","w");
31     fscanf(fin,"%d",&n);n++; 
32     x[1]=0;y[1]=0;
33     for(i=2;i<=n;i++){
34       fscanf(fin,"%d%d",&x[i],&y[i]);
35       a[i]=(double)y[i]/x[i];
36     }
37     qs(a,x,y,2,n);
38     for(i=2;i<=n;i++)
39      f[1][i]=1;
40     for(i=2;i<=n;i++)
41      {
42          for(j=i+1;j<=n+1;j++)
43           {
44               if(j==n+1) t=1;
45               else t=j;
46               for(k=1;k<=i-1;k++){
47                   if(judge(x[k],y[k],x[i],y[i],x[t],y[t]))
48                    if(f[k][i]+1>f[i][t])
49                     f[i][t]=f[k][i]+1;
50               }
51           }
52      }
53     for(i=2;i<=n;i++)
54      {
55          if(f[i][1]>ans) ans=f[i][1]; 
56      }
57     fprintf(fout,"%d
",ans);
58     fclose(fin);
59     fclose(fout);
60     return 0;
61 }

最后写一点总结性的，算是为以后再看时留下更有用的信息：此题动态规划时前后区间均要扫面全面，才可以使程序实现随时根据最优情况做出调成的功能。

（第一篇草草写完，很激动，吃饭去了）

——励志不做copy王