hdu - 4709 - Herding

題意：給出N個點的坐標，從中取些點來組成一個多邊形，求這個多邊形的最小面積，組不成多邊形的輸出"Impossible"（測試組數 T <= 25, 1 <= N <= 100,  -1000 <= 坐標Xi, Yi <= 1000）。       ——>>面積最小，若有的話，一定是三角形。判斷3點是否能組成一個三角形，若用斜率來做，麻煩且可能會有精度誤差，用叉積來判斷甚好（只需判斷兩向量的叉積是否為0）。   注意：N可為1、2，這時不能判斷三角形。

 
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
  
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;  
}