自动搬运

查看原文

来自洛谷，原作者为

	dc_ansan_tangmingyi 无条件互关||忘关私||初一蒟蒻一枚||AT号:dcsugar||CF号:sugarbean

搬运于2025-08-24 23:01:56，当前版本为作者最后更新于2024-08-11 20:25:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

题意：

给定 $n$ 个点，选任意 $3$ 个点，求着 $3$ 个点所形成的图形的最小面积。

思路：

由于 $n \le 100$ ，所以暴力枚举即可。时间复杂度 $O(n^3)$ 。

AC CODE:

#include<bits/stdc++.h>
using namespace std; 
double x[105] , y[105]; 
double area(double x1 , double y1 , double x2 , double y2 , double x3 , double y3){ //求面积函数
	return 0.5 * (x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2); 
}
void solve(){
    int n; 
    cin >> n; 
    for(int i = 1; i <= n; i ++){
    	cin >> x[i] >> y[i]; 
    }
    
    double ans = 1e18;
    //枚举3个点
    for(int i = 1; i <= n; i ++){
    	for(int j = i + 1; j <= n; j ++){
    		for(int k = j + 1; k <= n; k ++){
    			double t = area(x[i] , y[i] , x[j] , y[j] , x[k] , y[k]); 
    			t = fabs(t); 
    			if(t <= 0.0) continue; //注意面积不能为0
    			ans = min(ans , t); 
    		}
		}
	}
    			
    if(ans == 1e18) cout << -1 << endl; 
    else cout << ans << endl;
}
int main(){
	int T; 
	cin >> T; 
	while(T --) solve(); 
	return 0; 
}