【CCCC】L3-021 神坛 (30分)计算几何+求三角形面积（极角排序）

problem

L3-021 神坛 (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
样例解释
输出的数值等于图中红色或紫色框线的三角形的面积。

• 平面上n个点，选3个，
• 求能组成的最小面积

solution

• 对于每个点，向其他所有点连一条向量，然后按照斜率从小到大（逆时针）排序
• 对于点ABC构成的最小三角形，直线AB与AC肯定是相邻的边，扫一遍就好
• 三角形的面积=abs(x1*y2-y2*x1)/2
• 5*1e9的数据，记得开longlong+double

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;

struct point{LL x, y;}pp[maxn], tmp[maxn];
bool cmp(point a, point b){return a.x*b.y>a.y*b.x;}

int main(){
	int n;  cin>>n;
	for(int i = 0; i < n; i++)
		cin>>pp[i].x>>pp[i].y;
	double ans = 1e18;
	for(int i = 0; i < n; i++){
		int cc = 0;
		for(int j = 0; j < n; j++){
			if(i==j)continue;
			tmp[cc].x = pp[j].x-pp[i].x;
			tmp[cc].y = pp[j].y-pp[i].y;
			cc++;
		}
		sort(tmp,tmp+cc,cmp);
		for(int j = 0; j < cc; j++)
			ans=min(ans,abs(0.5*(tmp[j].x*tmp[(j+1)%cc].y-tmp[(j+1)%cc].x*tmp[j].y)));
	}
	printf("%.3f\n",ans);
	return 0;
}




  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/109171937