这周的动规……
////题目描述////
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
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10
POLYGON.OUT
8
首先要先按各点与原点的斜率排个序，这样按顺序查找才能找出多边形。
一开始的想法是类似于求不上升链的动规：对于每一个点作为顶点的多边形，f[i]为最大顶点数。f[i]=max{f[j]+1}，转移条件是形成凸多边形。
而形成凸多边形的判断用了连接之前最后的两个点的法向量与新点的方向向量的数量积的正负。
1
2
3
4
5
6
7
8
9
10
11
| int judge(int vx1,int vy1,int vx2,int vy2){
int t;
int sum;
t=vx1;
vx1=vy1;
vy1=t;
vx1=(-vx1);
sum=vx1*vx2+vy1*vy2;
if(sum>0)return 1;
return 0;
}
|
结果傻乎乎地写下了如下程序……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| a[1].v_x=a[1].x;
a[1].v_y=a[1].y;
f[1]=1;
for(i=2;i<=n;i++){
f[i]=1;
a[i].v_x=a[i].x;
a[i].v_y=a[i].y;
for(j=1;j<i;j++){
vx=a[i].x-a[j].x;
vy=a[i].y-a[j].y;
if(f[i]<f[j]+1&&judge(a[j].v_x,a[j].v_y,vx,vy)){
f[i]=f[j]+1;
a[i].v_x=vx;
a[i].v_y=vy;
}
}
}
|
然后就发现不对了，我将节点与上一个节点的向量储存，并作为下一次拓展的前提；但是这个保存的向量未必是最优的 ！这就意味着这个向量也需要转移……
我又在一维DP的路上走了下去……
1
2
3
4
5
6
7
8
9
| float vector(int x,int y){
float base=sqrt(x*x+y*y);
return (x/base);
}
if(vector(a[i].v_x,a[i].v_y)<vector(vx,vy)){
a[i].v_x=vx;
a[i].v_y=vy;
}
|
越改越乱……
实际上我从将向量存在struct node的a[i].v_x,a[i].v_y时就出了偏差……这个时候就要二维动规就能解决问题了……
f[i][j]为以i,j两点为最后两顶点的多边形的最大顶点数（就是之前那个死活搞不对的向量）
f[i][j]=max{f[i][j],f[k][i]+1}
所以最后……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node{
float x,y;
float slope;
};
struct node a[200]={0};
int judge(float vx1,float vy1,float vx2,float vy2){
float t;
float sum;
t=vx1;
vx1=vy1;
vy1=t;
vx1=(-vx1);
sum=vx1*vx2+vy1*vy2;
if(sum>0)return 1;
return 0;
}
void qqsort(int left,int right) {
int i,j;
float mid;
struct node t;
i=left;
j=right;
mid=a[(i+j)/2].slope;
do{
while(a[i].slope<mid)i++;
while(a[j].slope>mid)j--;
if(i<=j){
t=a[i];a[i]=a[j];a[j]=t;i++;j--;
}
}while(i<=j);
if(left<j)qqsort(left,j);
if(i<right)qqsort(i,right);
}
int main(){
int n,i,j,k,max=0;
float vx,vy,vkx,vky;
int f[200][200]={0};
FILE *fin,*fout;
fin=fopen("polygon.in","r");
fout=fopen("polygon.out","w");
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%f%f",&a[i].x,&a[i].y);
a[i].slope=a[i].y/a[i].x;
}
a[0].x=0;
a[0].y=0;
a[n+1].x=0;
a[n+1].y=0;
qqsort(1,n);
for(i=1;i<=n;i++)
f[0][i]=1;
for(i=0;i<=n;i++)
for(j=i+1;j<=n+1;j++){
f[i][j]=1;
vx=a[i].x-a[j].x;
vy=a[i].y-a[j].y;
for(k=0;k<i;k++){
vkx=a[k].x-a[i].x;
vky=a[k].y-a[i].y;
if(judge(vkx,vky,vx,vy)&&f[i][j]<f[k][i]+1)
f[i][j]=f[k][i]+1;
}
}
for(i=0;i<=n;i++)
for(j=1;j<=n+1;j++){
if(max<f[i][j])max=f[i][j];
}
fprintf(fout,"%d\n",max);
fclose(fin);
fclose(fout);
return 0;
}
蛮好玩的ヽ(￣▽￣)ﾉ
|