本文主要是介绍PTA:7-4 神坛 (30 分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目
在古老的迈瑞城,巍然屹立着 n 块神石。长老们商议,选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比,因此神坛的面积越小越好。特殊地,如果有两块神石坐标相同,或者三块神石共线,神坛的面积为 0.000。
长老们发现这个问题没有那么简单,于是委托你编程解决这个难题。
输入格式:
输入在第一行给出一个正整数 n(3 ≤ n ≤ 5000)。随后 n 行,每行有两个整数,分别表示神石的横坐标、纵坐标(−10
9
≤ 横坐标、纵坐标 <10
9
)。
输出格式:
在一行中输出神坛的最小面积,四舍五入保留 3 位小数。
输入样例:
8
3 4
2 4
1 1
4 1
0 3
3 0
1 3
4 2
输出样例:
0.500
样例解释
输出的数值等于图中红色或紫色框线的三角形的面积。
二、相关知识
1.极角排序
极角排序相关知识
2.通过极角排序再给根据叉积可以得出最小的面积
通过画图,可以得知,相邻边构成的三角形中有最小的三角形
三、代码
//神坛,极角排序
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{long long x,y;//坐标 int xiang;// 象限
};
int n;
bool cmp(node x,node y)
{//排序方法,先按象限排序,在按大小排序 if(x.xiang!=y.xiang)return x.xiang<y.xiang;return x.x*y.y-x.y*y.x<0;
}
int judge(node x)
{//判断象限if(x.x>0&&x.y>0) return 1;if(x.x<0&&x.y>0) return 2;if(x.x<0&&x.y<0) return 3;if(x.x>0&&x.y<0) return 4;}
int main()
{cin>>n;struct node a[5010],b[5010];for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}double s=-1;int cnt;for(int i=1;i<=n;i++){cnt=1;for(int j=1;j<=n;j++){if(i==j) continue;//相同跳过 b[cnt].x=a[j].x-a[i].x;b[cnt].y=a[j].y-a[i].y;b[cnt].xiang=judge(b[cnt]);cnt++;} sort(b+1,b+n,cmp);for(int j=1;j<n-1;j++){//面积等于两条边向量的叉积 //int s1=fabs(b[j+1].x*b[j].y-b[j+1].y*b[j].x);//取绝对值 if(s==-1||fabs(b[j+1].x*b[j].y-b[j+1].y*b[j].x)*0.5<s)s=fabs(b[j+1].x*b[j].y-b[j+1].y*b[j].x)*0.5;}}printf("%.3f\n",s);return 0;}
程序是蓝色的诗
这篇关于PTA:7-4 神坛 (30 分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!