首页 > > 程序设计 > C/C++ >

Maximal Area Quadrilateral CodeForces - 340B …

2018-06-17 21:50:23来源：未知阅读 ()

Maximal Area Quadrilateral CodeForces - 340B

三点坐标求三角形面积（可以带正负，表示向量/点的不同相对位置）：

http://www.cnblogs.com/xiexinxinlove/p/3708147.html

https://jingyan.baidu.com/article/a65957f49596ab24e67f9be7.html

枚举对角线，求出在对角线两侧取任意点能得到的三角形的面积，然后对于每条对角线，最大值就是两侧面积最大值之和。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using std::max;
 4 #include<cmath>
 5 using std::abs;
 6 #define inf 20000000.0
 7 int n;
 8 double x[310],y[310],a[2],anss,mj1;
 9 double mj(double x1,double y1,double x2,double y2,double x3,double y3)
10 {
11     return ((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))/2;
12 }
13 int main()
14 {
15     int i,j,k;
16     scanf("%d",&n);
17     for(i=1;i<=n;i++)
18         scanf("%lf%lf",&x[i],&y[i]);
19     for(i=1;i<=n;i++)
20         for(j=i+1;j<=n;j++)
21         {
22             a[0]=a[1]=-inf;
23             for(k=1;k<=n;k++)
24             {
25                 if(k==i||k==j)    continue;
26                 mj1=mj(x[i],y[i],x[j],y[j],x[k],y[k]);
27                 a[mj1>0]=max(a[mj1>0],abs(mj1));
28             }
29             anss=max(anss,a[0]+a[1]);
30         }
31     printf("%lf",anss);
32     return 0;
33 }