做网站建设 个体经营 小微企业,全球网站建设品牌,网站制作的市场前景,郑州市网站题面 题意:给你一堆点,求一个最大面积的空凸包,里面没有点. 题解:红书板子,照抄完事,因为题目给的都是整点,所以最后答案一定是.5或者.0结尾,不用对答案多做处理 1 #includebits/stdc.h2 #define N 553 using namespace std;4 struct rec5 {6 double x,y;7 };8 rec…题面 题意:给你一堆点,求一个最大面积的空凸包,里面没有点. 题解:红书板子,照抄完事,因为题目给的都是整点,所以最后答案一定是.5或者.0结尾,不用对答案多做处理 1 #includebits/stdc.h2 #define N 553 using namespace std;4 struct rec5 {6 double x,y;7 };8 rec operator -(rec a,rec b)9 {
10 rec c;
11 c.xa.x-b.x;
12 c.ya.y-b.y;
13 return c;
14 }
15 double sqr(double a)
16 {
17 return a*a;
18 }
19 int sign(double a)
20 {
21 if (fabs(a) 1e-6) return 0;
22 return a0?-1 :1;
23 }
24 bool operator (rec a,rec b)
25 {
26 return sign(b.y-a.y)0 || sign(b.y-a.y)0 sign(b.x-a.x)0;
27 }
28 double max(double a,double b)
29 {
30 return ab ?a:b;
31 }
32 double length(rec a)
33 {
34 return sqrt(sqr(a.x)sqr(a.y));
35 }
36 double cross(rec a,rec b)
37 {
38 return a.x*b.y-a.y*b.x;
39 }
40 rec dot[N],lis[N];
41 double opt[N][N];
42 int seq[N],n,len;
43 double ans;
44 bool Compare(rec a,rec b)
45 {
46 int tempsign(cross(a,b));
47 if (temp!0) return temp0;
48 tempsign(length(b)-length(a));
49 return temp0;
50 }
51 void solve(int vv)
52 {
53 int t,i,j,_len;
54 for (ilen0;in;i)
55 if (dot[vv]dot[i]) lis[len]dot[i]-dot[vv];
56 for (int i0;ilen;i)
57 for (int j0;jlen;j)
58 opt[i][j]0;
59 sort(lis,lislen,Compare);
60 double v;
61 for (t1;tlen;t)
62 {
63 _len0;
64 for (it-1;i0 sign(cross(lis[t],lis[i])) 0 ;i--);
65 while (i0)
66 {
67 vcross(lis[i],lis[t])/2;
68 seq[_len]i;
69 for (ji-1; j0 sign(cross(lis[i]-lis[t], lis[j]-lis[t])) 0 ;j--);
70 if (j0) vopt[i][j];
71 ansmax(ans,v);
72 opt[t][i]v;
73 ij;
74 }
75 for (i _len-2;i0;i--)
76 opt[t][seq[i]]max(opt[t][seq[i]],opt[t][seq[i1]]);
77 }
78 }
79 int T;
80 int main()
81 {
82 scanf(%d,T);
83 while (T--)
84 {
85 scanf(%d,n);
86 for (int i0;in;i) scanf(%lf%lf,dot[i].x,dot[i].y);
87 ans0;
88 for (int i0;in;i) solve(i);
89 printf(%.1lf\n,ans);
90 }
91 return 0;
92 } 转载于:https://www.cnblogs.com/qywhy/p/9741184.html
