Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 用叉积公式可以加速计算面积

Posted by yygy at 2023-05-25 16:19:54 on Problem 3587
```// MyFirstApp.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <map>
#include <algorithm>

using namespace std;

typedef __int64 lld;

const int MAXN = 512;

const double pi = acos(-1.0);

//经度角a, 纬度角b
double GeodesicDistance(double r, double a1, double b1, double a2, double b2)
{
return r * acos(cos(b1) * cos(b2) * cos(a1 - a2) + sin(b1) * sin(b2));
}

struct Point
{
int x, y;

Point operator -(const Point& other) const
{
Point result;
result.x = x - other.x;
result.y = y - other.y;
return result;
}

Point operator +(const Point& other) const
{
Point result;
result.x = x + other.x;
result.y = y + other.y;
return result;
}

int operator ^(const Point& other) const
{
return x* other.y - other.x * y;
}

};

static void Rotate90(Point& dir)
{
double x = -dir.y;
double y = dir.x;
dir.x = x;
dir.y = y;
}

double Distance(const Point& a, const Point& b)
{
int dx = a.x - b.x;
int dy = a.y - b.y;
return sqrt(dx * dx * 1.0 + dy * dy);
}

int DoubleCompare(double a, double b)
{
if (fabs(a - b) < 1e-6)
{
return 0;
}

return a < b ? -1 : 1;
}

Point p[1024];

double dis[1024][1024];

int main()
{
int n=500;
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
}

double maxR = 0;

for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
dis[i][j] = dis[j][i] = Distance(p[i], p[j]);

if (dis[i][j] / 2 > maxR)
{
maxR = dis[i][j] / 2;
}
}
}

for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int k = j + 1; k < n; k++)
{
//a^2 b^2 c^2 /16 S
//abc/4S
int crossValue = (p[j] - p[i]) ^ (p[k] - p[i]);
double tmp = dis[i][j] * dis[j][k] * dis[i][k] / fabs(crossValue * 2);

if (tmp > maxR)
{
maxR = tmp;
}
}
}
}

printf("%.3f\n", maxR);
}

return 0;
}

/*

*/
```

Followed by: