题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=10

 

题意：  给定n个点的， 如果这n个点不能形成多边形 以及 n < 3 时， 输出， “Impossible”，  否则 输出 多边形的面积。

分析：

这题主要在 分析  n 个点 是否形成 多边形。  枚举 每条边，  看 这条边 是否与 其他 n - 3 条边 不规范相交。 （当处理 其他 边时， 我们采用 扩充线段一倍）

 

代码如下：

const int Max_N = 1010 ;double add(double a, double b){    if( fabs(a + b) < EPS * ( fabs(a) + fabs (b)) ) return 0 ;    return a + b ;}struct Point{    double x, y ;    Point(){}    Point(double x , double y):x(x),y(y){}    Point operator +( Point p){        return Point(add(x , p. x) , add(y , p.y) ) ;    }    Point operator -( Point p){        return Point(add(x ,- p. x) , add(y ,- p.y) ) ;    }    Point operator * (double d){        return Point( x*d , y * d ) ;    }    double operator * (Point p){        return add(x * p.x , y * p.y) ;    }    double operator ^(Point p){        return add(x * p.y , -y*p.x) ;    }}po[Max_N];//判断点p是否在线段p1p2内int on_segment(Point p1, Point p2, Point p){    if( ((p1 - p).x * (p2 - p).x <= 0) &&   ((p1 - p).y * (p2 - p).y <= 0))        return 1;    return 0;}struct Line{    Point st, ed;    Line(){}    Line(Point a, Point b){    st = a ;    ed = b ;    }}line[Max_N *2];//判断线段p1p2与q1q2 是否相交int intersection(Line l1, Line l2 ){    Point p1 , p2 ,q1, q2 ;    p1 = l1.st ;    p2 = l1.ed ;    q1 = l2.st ;    q2 = l2.ed ;    double d1, d2, d3, d4;    d1 = (p2 - p1)^(q1 - p1) ;    d2 = (p2 - p1)^(q2 - p1) ;    d3 = (q2 - q1)^(p1 - q1) ;    d4 = (q2 - q1)^(p2 - q1) ;    if((d1 == 0 && on_segment(p1, p2, q1))    || (d2 == 0 && on_segment(p1, p2, q2))    || (d3 == 0 && on_segment(q1, q2, p1))    || (d4 == 0 && on_segment(q1 ,q2 ,p2)))        return 1;    else if(d1 * d2 < 0 && d3 * d4 < 0)        return 1;    return 0;}int  n;bool judge(){    int i , j ;    for(i = 0 ;  i < n ; i++)        for(j = i + 2; j <= n+ i - 2 ; j++)            if( intersection( line[i] , line[j]) )                return 0 ;    return 1;}int main(){    int  i , j , k =1;    while(scanf("%d" , &n) && n){        double area = 0.0 ;        for(i = 0 ; i < n ; i++)            scanf("%lf%lf", &po[i].x , &po[i].y) ;        for(i =0 ;i < n ; i++){            line[i].st = po[i];            line[i].ed = po[(i+1) % n ] ;        }        for(i = 0 ; i< n ; i++)   // 把线段扩展一倍时，特别好处理， 与线段不相邻的其他线段            line[n + i] = line[i] ;        if( k != 1) puts("") ;        printf("Figure %d: ", k++) ;         if(n < 3)        {            printf("Impossible\n") ;            continue ;        }        if(judge()){            for(i = 0 ;i < n ; i++)            area += po[i]^po[ (i+1) % n ] ;        area = area < 0 ? -area : area ;        printf("%.2lf\n" , area / 2.0 ) ;        }        else{            printf("Impossible\n") ;        }    }    return 0;}