P10859 [HBCPC2024] Nana Likes Polygons 题解

Cyx20110930 · 2024-08-12 10:26:15 · 题解

简要题意

平面上有一些点，问你由其中至少三个点组成的图形的面积最小是几，如果组成不了图形，输出 -1。

Sol

很明显最小的一定是三角形。

感性证明：任何一个正 n 边形，都可以分成一个三角形，与一个正 n-1 边形，自然三角形的面积小于这个正 n 边形。

所以枚举三个点，不断刷新面积最小值就行了。

Code

注意特判三点共线！

#include <bits/stdc++.h>
using namespace std;
struct node{
    double x,y;
}po[1000005];
void solve(){
    double ans=0x3f;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>po[i].x>>po[i].y;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int z=j+1;z<=n;z++){
                double sum=po[j].x*po[z].y-po[z].x*po[j].y+po[i].x*po[j].y-po[j].x*po[i].y-po[i].x*po[z].y+po[z].x*po[i].y;
                sum=abs(sum);
                if (sum != 0){
                    ans=min(ans,sum/2.0);
                }
            }
        }
    }
    if (ans==0x3f){
        cout<<-1<<endl;
    }
    else{
        cout<<ans<<endl;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}