Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator