三角形的面积

绝地灬酷狼 2022-08-05 02:54 202阅读 0赞

Problem Description

老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。

Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。

Input

输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3<= n <= 50000 而且 -10000 <= xi, yi <= 10000.

Output

对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。

每组输出占一行。

Sample Input

3

3 4

2 6

3 7

6

2 6

3 9

2 0

8 0

6 6

7 7

Sample Output

1.50

27.00

参考代码：

#include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    struct Point{
    	double x,y;
    };
    double bian(Point p1,Point p2){
    	double x,y;
    	x=fabs(p1.x-p2.x);
    	y=fabs(p1.y-p2.y);
    	return sqrt(pow(x,2)+pow(y,2));
    }
    int main(){
    	int n,i,j,k;
    	double a,b,c,d,maxS=0,s;
    	Point*p;
    	scanf("%d",&n);
    	p=(Point*)malloc(sizeof(Point)*n);
    	for(i=0;i<n;i++){
    		scanf("%lf %lf",&p[i].x,&p[i].y);
    	}
    	for(i=0;i<n;i++){
    		for(j=i+1;j<n;j++){
    			for(k=j+1;k<n;k++){
    				a=bian(p[i],p[j]);
    				b=bian(p[i],p[k]);
    				c=bian(p[j],p[k]);
    				d=(a+b+c)/2;
    				s=sqrt(d*(d-a)*(d-b)*(d-c));
    				if(s>maxS)
    					maxS=s;
    			}
    		}
    	}
    	printf("%.2lf\n",maxS);
    	return 0;
    }

测试结果：

![SouthEast][]

![SouthEast 1][]

[SouthEast]: /images/20220805/3e3381c6fa2f4d6fbd0e76f3a3ffd4c5.png
[SouthEast 1]: /images/20220805/6cf11181f98d4662b2190ac161fff850.png

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关 c语言求三角形的面积

要求三角形的面积，首先需要知道三角形的三边长。假设三角形的三边长分别为a、b、c，可以使用海伦公式计算三角形的面积：面积 = sqrt(p \ (p - a) \ (p -

深藏阁楼爱情的钟/ 2024年02月20日 09:36/ 0 赞/ 47 阅读

相关编程三角形面积公式_三角形面积公式110式（英文版）

点击上面蓝色文字关注杨志明数学角精华博览 8年新课标I、5年新课标II、4年新课标III高考数学真题

偏执的太偏执、/ 2023年01月06日 12:59/ 0 赞/ 223 阅读

相关三角形面积公式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我就是我/ 2022年12月10日 03:47/ 0 赞/ 218 阅读

相关三角形的面积

如图所示，三角形魔法阵是魔法师公认的最强大的阵形之一，因为三角形有着稳固、坚定、耐压的特点。现输入三角形的三边长，求三角形面积（假设输入的a，b，c能构成三角形）。输入

水深无声/ 2022年11月07日 04:18/ 0 赞/ 190 阅读

相关 NYOJ 67 三角形面积

三角形面积时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述给你三个点，表示一个三角形的三个顶点，现你的任务是求出该三角形的面积

深藏阁楼爱情的钟/ 2022年09月19日 04:22/ 0 赞/ 164 阅读

相关求三角形面积

求三角形面积 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述多组（约100组处理<

浅浅的花香味﹌/ 2022年08月19日 02:21/ 0 赞/ 249 阅读

相关三角形的面积

Problem Description 老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角

绝地灬酷狼/ 2022年08月05日 02:54/ 0 赞/ 203 阅读

相关 C++ 计算三角形面积

C++编码实现计算三角形面积 1- 计算公式 1. 方法一： S=√\[p(p-a)(p-b)(p-c)\] ，而公式里的p为半周长：p=(a+b+c)/2 2.

ゝ一纸荒年。/ 2022年05月28日 02:39/ 0 赞/ 1126 阅读

相关 acm 正三角形的外接圆面积

正三角形的外接圆面积时间限制：1000 ms | 内存限制：65535 KB 难度：0 输入只有一组测试数据第一行输入一个整数n(1<n<1000)表示接

逃离我推掉我的手/ 2022年05月17日 12:28/ 0 赞/ 169 阅读

相关【算法】计算三角形面积

题目平面上有一个三角形，它的三个顶点坐标分别为(x1, y1), (x2, y2), (x3, y3)，那么请问这个三角形的面积是多少，精确到小数点后两位。。 In

Myth丶恋晨/ 2022年03月31日 16:48/ 0 赞/ 310 阅读