Codeforces Round #198 (Div. 二) B. Maximal Area Quadrilateral

Codeforces Round #198 (Div. 2) B. Maximal Area Quadrilateral

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: x_i, y_i ( - 1000 ≤ x_i, y_i ≤ 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.

Sample test(s)

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 is 4·4 = 16.

思路：

将四边形看做两个三角形，枚举两个点，构成一条线段，扫描其它点，找到线段两侧的最远点，这四个点构成的三角形最大。复杂度为O(n^3)，不会TLE。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#define maxn 305
using namespace std;

int n,m;
double ans;
struct Node
{
    int x,y;
}pp[maxn],p1,p2,p3;

double caldist(Node tt)
{
    return sqrt(tt.x*tt.x*1.0+tt.y*tt.y);
}
double Det(Node pp1,Node pp2)   // 计算向量叉积
{
    return pp1.x*pp2.y-pp2.x*pp1.y;
}
void solve()
{
    int i,j,k,dir;
    double d1,d2,dd,t;
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            p1.x=pp[j].x-pp[i].x;
            p1.y=pp[j].y-pp[i].y;
            d1=d2=0;
            for(k=1;k<=n;k++)
            {
                if(k==i||k==j) continue ;
                p2.x=pp[k].x-pp[i].x;
                p2.y=pp[k].y-pp[i].y;
                dd=Det(p1,p2);
                if(dd<0) dir=-1;
                else dir=1;
                t=fabs(dd/caldist(p1));
                if(dir==-1)
                {
                    if(d1<t) d1=t;
                }
                else
                {
                    if(d2<t) d2=t;
                }
            }
            if(d1&&d2) ans=max(ans,0.5*caldist(p1)*(d1+d2)); // 有一边没有找到的话就不要更新了
        }
    }
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&pp[i].x,&pp[i].y);
        }
        ans=0;
        solve();
        printf("%.10f\n",ans);
    }
    return 0;
}

Codeforces Round #198 (Div. 二) B. Maximal Area Quadrilateral

相关推荐