B. Maximal Area Quadrilateral(叉积模板)

B. Maximal Area Quadrilateral time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

Input

The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.

Output

Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10 - 9.

Examples input 5 0 0 0 4 4 0 4 4 2 3 output 16.000000 Note

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is4·4 = 16.

题目大意:给你很多坐标轴上的点，求任意四个点组成的四边形最大面积

解题思路:这是我遇到为数不多的数学题，它的主要思想是叉积，这道题就是求任意两个点组成的四边形的对角线，然后在这条线的左右两边各取一个点，使之左边的三角形最大，右边的三角形最大，合起来就是最大的四边形面积，而如何判断是在对角线的哪一边，用到的就是叉积，也就是我的代码across函数

#include<iostream> #include<cstdio> #include<stdio.h> #include<cstring> #include<cstdio> #include<climits> #include<cmath> #include<vector> #include <bitset> #include<algorithm> #include <queue> #include<map> using namespace std; double ans,lmax, rmax; struct point { double x, y; }p[308]; double max(double a,double b) { if (a > b) { return a; } else { return b; } } double across(point a, point b, point c) { return ((a.x - c.x)*(b.y - c.y) - (b.x - c.x)*(a.y - c.y))/2; } int main() { int n, i, j, k; cin >> n; for (i = 1; i <= n; i++) { cin >> p[i].x >> p[i].y; } ans = 0; for (i = 1; i <= n; i++) { for (j = i + 1; j <= n; j++) { lmax = 0; rmax = 0; for (k = 1; k <= n; k++) { if (k == i || k == j) { continue; } double s = across(p[i], p[j], p[k]); if (s <= 0) { lmax = max(lmax, -s); } else { rmax = max(rmax, s); } } if (lmax == 0 || rmax == 0) { continue; } ans = max(ans, (lmax + rmax)); } } printf("%lf\n", ans); }