小红的平行四边形时间限制2秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红在平面上有n nn个点她准备选择其中四个点画一个平行四边形。请你帮小红求出平行四边形的最大面积。输入描述第一行输入一个正整数n nn代表点的数量。接下来的n nn行每行输入2 22个整数x i x_ixi​​和y i y_iyi​​代表第i ii个点的坐标。4 ≤ n ≤ 1000 4≤n≤10004≤n≤1000− 10 9 ≤ x i , y i ≤ 10 9 −10^9≤x_i,y_i≤10^9−109≤xi​,yi​≤109保证不存在两个重合的点。输出描述如果不存在平行四边形请输出− 1 -1−1。否则输出一个浮点数代表平行四边形的面积。保留一位小数。示例1输入5 0 0 0 1 1 0 1 1 2 1输出1.0说明选前四个点即可正方形也是平行四边形解题思路本题核心利用平行四边形对角线互相平分的几何性质求解将问题转化为中点分组向量叉乘计算。四个点能构成平行四边形的充要条件是两对角线的中点坐标完全相同。枚举所有点对以中点为键将点对分组同一组内的任意两组点对均可构成平行四边形。平行四边形的面积通过向量叉乘计算面积两邻边向量叉乘的绝对值。遍历所有分组计算所有合法组合的面积并记录最大值若无合法平行四边形输出-1。算法时间复杂度O ( n 2 ) O(n^2)O(n2)完美适配n ≤ 1000 n \le 1000n≤1000的数据范围。总结核心逻辑平行四边形对角线中点重合通过中点分组枚举所有合法四边形。关键操作枚举点对计算中点、哈希表分组存储、向量叉乘求面积。效率保障平方级复杂度适配题目约束精准求解最大面积并判断无解场景。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;usingNodearrayll,2;voidsolve(){ll n;cinn;vectorNodea(n);for(auto[x,y]:a)cinxy;sort(a.begin(),a.end());mapNode,vectorNodemp;for(ll i0;in;i)for(ll j0;jn;j)if(i!j){auto[xi,yi]a[i];auto[xj,yj]a[j];mp[{xj-xi,yj-yi}].push_back({xi,yi});}ll ans0;for(auto[u,v]:mp){ll xu[0];ll yu[1];sort(v.begin(),v.end(),[](Nodep1,Nodep2){auto[x1,y1]p1;auto[x2,y2]p2;returnx1*y-y1*xx2*y-y2*x;});if(v.size()!1){auto[x1,y1]v.front();auto[x2,y2]v.back();ll ps(x2*y-y2*x)-(x1*y-y1*x);ansmax(ans,ps);}}if(ans)coutans.0endl;elsecout-1endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;//cint;for(ll i0;it;i)solve();return0;}