hdu - 4709 - Herding - c++编程基础

题意：给出N个点的坐标，从中取些点来组成一个多边形，求这个多边形的最小面积，组不成多边形的输出"Impossible"（测试组数 T <= 25, 1 <= N <= 100, -1000 <= 坐标Xi, Yi <= 1000）。

——>>面积最小，若有的话，一定是三角形。判断3点是否能组成一个三角形，若用斜率来做，麻烦且可能会有精度误差，用叉积来判断甚好（只需判断两向量的叉积是否为0）。

注意：N可为1、2，这时不能判断三角形。

 
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 100 + 10;  
const double eps = 1e-10;  
const double INF = 1 << 30;  
  
int N;  
  
struct Point{  
    double x;  
    double y;  
    Point(double x = 0, double y = 0):x(x), y(y){}  
}p[maxn];  
  
typedef Point Vector;  
  
Vector operator + (Point A, Point B){  
    return Vector(A.x + B.x, A.y + B.y);  
}  
  
Vector operator - (Point A, Point B){  
    return Vector(A.x - B.x, A.y - B.y);  
}  
  
Vector operator * (Point A, double p){  
    return Vector(A.x * p, A.y * p);  
}  
  
Vector operator / (Point A, double p){  
    return Vector(A.x / p, A.y / p);  
}  
  
double Cross(Vector A, Vector B){  
    return A.x * B.y - B.x * A.y;  
}  
  
double Area2(Point A, Point B, Point C){  
    return Cross(B-A, C-A);  
}  
  
int dcmp(double x){  
    if(fabs(x) < eps) return 0;  
    else return x < 0   -1 : 1;  
}  
  
void read(){  
    scanf("%d", &N);  
    for(int i = 0; i < N; i++) scanf("%lf%lf", &p[i].x, &p[i].y);  
}  
  
void solve(){  
    double Min = INF;  
    if(N >




= 3){  
        for(int i = 0; i < N; i++)  
        for(int j = i+1; j < N; j++)  
            for(int k = j+1; k < N; k++) if(dcmp(Cross(p[j] - p[i], p[k] - p[i]))){  
                double temp = fabs(Area2(p[i], p[j], p[k]));  
                Min = min(Min, temp);  
            }  
    }  
    if(dcmp(Min - INF) == 0) puts("Impossible");  
    else printf("%.2f\n", Min/2);  
}  
  
int main()  
{  
    int T;  
    scanf("%d", &T);  
    while(T--){  
        read();  
        solve();  
    }  
    return 0;  
}