| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用叉积公式可以加速计算面积// 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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator