今天杭电热身赛的一道题。据说是中山大学命题。。。。题目总体还是很有水平的。
先说下这个题的题意:
告诉你很多个点的坐标,让你用这些点来求面积最小的三角形的面积。
由于题中的数据量比较小,比赛中就直接暴力了。
具体实现来看看代码
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> using namespace std; const int vMaxsize = 105; const double inf = 999999.0; typedef struct { double x,y; }Point; Point point[vMaxsize]; double s(Point a,Point b,Point c)/*三点求三角形面积*/ { return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x - a.x))/2; } int main() { int ncase; scanf("%d",&ncase); double ans,tmp; while(ncase--) { bool flag = false; tmp = 0.0; ans = inf; int n; scanf("%d",&n); for(int i = 0 ; i < n ; i++) { scanf("%lf %lf",&point[i].x,&point[i].y); } for(int i = 0 ; i < n ; i++)/*三重循环暴力*/ { for(int j = 0 ; j < n ; j++ ) { if( i != j) { for(int k = 0 ; k < n ; k++) { if( k != j && k != i) { tmp = s(point[i],point[j],point[k]); tmp = fabs(tmp); if(tmp < ans && tmp != 0.0)/*tmp == 0 ,表示三点共线*/ { ans = tmp; flag = true; } } } } } } if(flag) { printf("%.2lf\n",ans); } else { printf("Impossible\n"); } } return 0; }