codeforces 340B Maximal Area Quadrilateral（叉积）

事实再一次证明：本小菜在计算几何上就是个渣= =

题意：平面上n个点(n<=300)，问任意四个点组成的四边形（保证四条边不相交）的最大面积是多少。

分析：

1、第一思路是枚举四个点，以O(n4)的算法妥妥超时。

2、以下思路源自官方题解

　　以O(n2)枚举每一条边，以这条边作为四边形的对角线（注意：这里所说的对角线是指把四边形分成两部分的线，不考虑凹四边形可能出现的两个点在对角线同一侧的情况），以O(n)枚举每一个点，判断是在对角线所在直线的左侧还是右侧。因为被对角线分割开的两三角形不相关，所以可以单独讨论：分别找出左右两侧的最大三角形，二者之和即为此边对应的最大四边形。整个算法为O(n3)。

3、何为叉积?

　　百度百科“叉积”解释的很详细，这里用到两条：

　　一、axb 表示的是一个符合右手法则的、垂直于a、b的向量c，|c|=|a|*|b|*sinθ，θ指向量a,b的夹角，即|c|是以a、b为边的平行四边形的面积——已知3点A,B,C，|BAxCA|==S(三角形ABC)*2。

　　二、坐标表示法中，a(x1,y1),b(x2,y2)。c=axb=x1*y2-x2*y1，c的正负表示方向，正为上、负为下。而在三维中，方向不能简单的以正负表示，所以只能以一个向量的形式来描述：

　　| i , j , k |

　　|x1,y1,z1|

　　|x2,y2,z2| i,j,k分别表示x轴、y轴、z轴上的单位向量，矩阵的解也就是c=axb。

　　这里只是二维平面，判断点在向量所在直线的哪一侧，就可以利用叉积的方向来区别。对角线AB，两侧各取一点C、D，必然有CAxCB=-DAxDB。

注意：一开始不知道叉积的模即是三角形面积的两倍，就用axb=|a|*|b|*cosθ推S=|a|*|b|*sinθ，跑到第八组数据就超时了，纠结了好久，后来发现，原来每个三角形是在O(n3)的复杂度下求解的，多算一步就多一个O(n3)，TLE的不冤T^T

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define rep(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int MAXN=;

 const double eps=1e-;

 struct Point{

     double x,y;

     Point(double _x=,double _y=):x(_x),y(_y){}

 }p[MAXN];

 typedef Point Vector;

 Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}

 double cross(Vector a,Vector b)

 {

     return (a.x*b.y-a.y*b.x)*0.5;

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     rep(i,,n){

         scanf("%lf%lf",&p[i].x,&p[i].y);

     }

     double ans=;

     rep(i,,n){

         rep(j,i+,n){

             double lmax,rmax;

             lmax=rmax=;

             rep(k,,n){

                 if(k==i||k==j)

                     continue;

                 double s=cross(p[i]-p[k],p[j]-p[k]);

                 if(s<eps)

                     lmax=max(lmax,-s);

                 else

                     rmax=max(rmax,s);

             }

             if(lmax==||rmax==)

                 continue;

             ans=max(ans,lmax+rmax);

         }

     }

     printf("%f\n",ans);

     return ;

 }

巴特西

codeforces 340B Maximal Area Quadrilateral（叉积）

最新文章

热门文章