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