http://poj.org/problem?id=1408
题意：
题意：有一个长 1 的正方形框（放在x-y坐标系的0-1上），然后给出一个数 n 代表该正方形每条边上的钉子数，接下来给出这钉子的坐标（按顺序且钉子没有重合的情况），把对边上的点依次按顺序用线连接起来，得到一张不规则的网，由多 个不过则四边形构成，输出这些小四边形中面积最大一块的面积。
题解：
首先将 四个边的点 保存， 根据题意 ，其中的四个点求出 点集p[][];
然后 在枚举多有的 多边形 得到面积的最大值
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 40
15 #define eps 1e-12
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 using namespace std;
20 struct point
21 {
22 double x;
23 double y ;
24 }p[maxn][maxn];
25
26 int n ;
27 double arr[maxn][maxn] ;
28 int dbcmp(double x)
29 {
30 if(fabs(x) < eps) return 0;
31
32 if(x < 0 ) return -1;
33 else return 1;
34 }
35 double det(double x1,double y1,double x2,double y2)
36 {
37 return x1*y2 - x2*y1;
38 }
39 double cross(point a,point b,point c)
40 {
41 return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
42 }
43 double dot(double x1,double y1,double x2,double y2)
44 {
45 return x1*x2 + y1 *y2 ;
46 }
47 double dotdet(double x1,double y1,double x2,double y2)
48 {
49 return x1*x2+y1*y2 ;
50 }
51 double dot(point a,point b,point c)
52 {
53 return dotdet(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
54 }
55 int betweencmp(point c,point a,point b)// c 是否在a ，b 间
56 {
57 return dbcmp(dot(c,a,b)) ;
58 }
59 point get (point a,point b,point c,point d)
60 {
61 point q;
62 double s1, s2,s3,s4;
63 int d1,d2,d3,d4;
64
65
66
67 d1 = dbcmp(s1 = cross(a,b,c));
68 d2 = dbcmp(s2 = cross(a,b,d));
69 d3 = dbcmp(s3 = cross(c,d,a));
70 d4 = dbcmp(s4 = cross(c,d,b));
71
72
73 if((d1^d2) == -2 &&(d3^d4) == -2)
74 {
75
76 q.x = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
77 q.y = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
78
79 return q ;
80 }
81
82 if(d1 == 0 && betweencmp(c,a,b) <= 0 ||
83 d2 == 0 && betweencmp(d,a,b) <= 0 ||
84 d3 == 0 && betweencmp(a,c,d) <= 0 ||
85 d4 == 0 && betweencmp(b,c,d) <= 0
86 )
87 {
88
89 q.x = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
90 q.y = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
91 return q ;
92 }
93
94
95
96 }
97
98 double area(point a,point b,point c,point d)
99 {
100 double s = 0;
101
102 s += det(a.x,a.y,b.x,b.y);
103 s += det(b.x,b.y,c.x,c.y);
104 s += det(c.x,c.y,d.x,d.y);
105 s += det(d.x,d.y,a.x,a.y);
106
107 return fabs(s*0.5);
108 }
109
110 void getpoint()
111 {
112 int i ,j;
113 p[1][1].x = 0;p[1][1].y = 0;//处理四个角
114 p[1][n + 2].x = 0;p[1][n + 2].y = 1;
115 p[n + 2][1].x = 1;p[n + 2][1].y = 0;
116 p[n + 2][n + 2].x = 1; p[n + 2 ][n + 2].y = 1;
117
118 for(i = 2;i<n + 2;i++)//处理四边
119
120 {
121 p[i][1].x = arr[1][i - 1];p[i][1].y = 0;
122 p[i][n + 2].x = arr[2][i - 1];p[i][n + 2].y = 1.0;
123 p[1][i].x = 0;p[1][i].y = arr[3][i - 1] ;
124 p[n + 2][i].x = 1;p[n + 2][i].y = arr[4][i - 1] ;
125 }
126
127 for(i = 2;i < n+ 2;i++)
128 {
129 for(j = 2;j< n+2;j++)
130 {
131 p[i][j] = get(p[i][1],p[i][n+2],p[1][j],p[n + 2][j]);
132 }
133 }
134 }
135 double gets()
136 {
137 int i,j;
138 double ans = 0.0;
139 for(i = 1;i <= n+1;i++)
140 {
141 for(j = 1;j <= n+1;j++)
142 {
143 double tmp = area(p[i][j],p[i + 1][j],p[i + 1][j + 1],p[i][j + 1]);//注意求面积时，四个点要按 逆时针转
144 if(tmp > ans ) ans = tmp ;
145 }
146 }
147 return ans ;
148 }
149
150 int main()
151 {
152 int i ,j;
153 //freopen("data.txt","r",stdin) ;
154 while(scanf("%d",&n),n)
155 {
156 for(i = 1 ;i<=4;i++)
157 {
158 for(j = 1;j<=n;j++)
159 {
160 scanf("%lf",&arr[i][j]);
161 }
162 }
163
164 getpoint();
165
166 double ans = gets();
167 printf("%.6lf\n",ans);
168 }
169 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 40
15 #define eps 1e-12
16 #define inf 100000000
17 #define mx 1<<60
18 #define ll __int64
19 using namespace std;
20 struct point
21 {
22 double x;
23 double y ;
24 }p[maxn][maxn];
25
26 int n ;
27 double arr[maxn][maxn] ;
28 int dbcmp(double x)
29 {
30 if(fabs(x) < eps) return 0;
31
32 if(x < 0 ) return -1;
33 else return 1;
34 }
35 double det(double x1,double y1,double x2,double y2)
36 {
37 return x1*y2 - x2*y1;
38 }
39 double cross(point a,point b,point c)
40 {
41 return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
42 }
43 double dot(double x1,double y1,double x2,double y2)
44 {
45 return x1*x2 + y1 *y2 ;
46 }
47 double dotdet(double x1,double y1,double x2,double y2)
48 {
49 return x1*x2+y1*y2 ;
50 }
51 double dot(point a,point b,point c)
52 {
53 return dotdet(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
54 }
55 int betweencmp(point c,point a,point b)// c 是否在a ，b 间
56 {
57 return dbcmp(dot(c,a,b)) ;
58 }
59 point get (point a,point b,point c,point d)
60 {
61 point q;
62 double s1, s2,s3,s4;
63 int d1,d2,d3,d4;
64
65
66
67 d1 = dbcmp(s1 = cross(a,b,c));
68 d2 = dbcmp(s2 = cross(a,b,d));
69 d3 = dbcmp(s3 = cross(c,d,a));
70 d4 = dbcmp(s4 = cross(c,d,b));
71
72
73 if((d1^d2) == -2 &&(d3^d4) == -2)
74 {
75
76 q.x = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
77 q.y = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
78
79 return q ;
80 }
81
82 if(d1 == 0 && betweencmp(c,a,b) <= 0 ||
83 d2 == 0 && betweencmp(d,a,b) <= 0 ||
84 d3 == 0 && betweencmp(a,c,d) <= 0 ||
85 d4 == 0 && betweencmp(b,c,d) <= 0
86 )
87 {
88
89 q.x = (c.x*s2 - d.x*s1)/(s2 - s1) ;// 求 交点 的 x 坐标
90 q.y = (c.y*s2 - d.y*s1)/(s2 - s1) ;// 求 交点 的 y 坐标
91 return q ;
92 }
93
94
95
96 }
97
98 double area(point a,point b,point c,point d)
99 {
100 double s = 0;
101
102 s += det(a.x,a.y,b.x,b.y);
103 s += det(b.x,b.y,c.x,c.y);
104 s += det(c.x,c.y,d.x,d.y);
105 s += det(d.x,d.y,a.x,a.y);
106
107 return fabs(s*0.5);
108 }
109
110 void getpoint()
111 {
112 int i ,j;
113 p[1][1].x = 0;p[1][1].y = 0;//处理四个角
114 p[1][n + 2].x = 0;p[1][n + 2].y = 1;
115 p[n + 2][1].x = 1;p[n + 2][1].y = 0;
116 p[n + 2][n + 2].x = 1; p[n + 2 ][n + 2].y = 1;
117
118 for(i = 2;i<n + 2;i++)//处理四边
119
120 {
121 p[i][1].x = arr[1][i - 1];p[i][1].y = 0;
122 p[i][n + 2].x = arr[2][i - 1];p[i][n + 2].y = 1.0;
123 p[1][i].x = 0;p[1][i].y = arr[3][i - 1] ;
124 p[n + 2][i].x = 1;p[n + 2][i].y = arr[4][i - 1] ;
125 }
126
127 for(i = 2;i < n+ 2;i++)
128 {
129 for(j = 2;j< n+2;j++)
130 {
131 p[i][j] = get(p[i][1],p[i][n+2],p[1][j],p[n + 2][j]);
132 }
133 }
134 }
135 double gets()
136 {
137 int i,j;
138 double ans = 0.0;
139 for(i = 1;i <= n+1;i++)
140 {
141 for(j = 1;j <= n+1;j++)
142 {
143 double tmp = area(p[i][j],p[i + 1][j],p[i + 1][j + 1],p[i][j + 1]);//注意求面积时，四个点要按 逆时针转
144 if(tmp > ans ) ans = tmp ;
145 }
146 }
147 return ans ;
148 }
149
150 int main()
151 {
152 int i ,j;
153 //freopen("data.txt","r",stdin) ;
154 while(scanf("%d",&n),n)
155 {
156 for(i = 1 ;i<=4;i++)
157 {
158 for(j = 1;j<=n;j++)
159 {
160 scanf("%lf",&arr[i][j]);
161 }
162 }
163
164 getpoint();
165
166 double ans = gets();
167 printf("%.6lf\n",ans);
168 }
169 }