主要判断是否是多边形：1、n<3 ； 2、非相邻两条线段不相交
#include <iostream> #include <cmath> #include <stdio.h> using namespace std; #define eps 1e-8 int sig(double x) { if(x<-eps) return -1; if(x>eps) return 1; return 0; } struct point { double x,y; } p[1005]; struct line { point p; point q; line() { } line(point aa,point bb) { p=aa; q=bb; } }; int inside(point o,line L) { double xl=min(L.p.x,L.q.x); double xr=max(L.p.x,L.q.x); double yl=min(L.p.y,L.q.y); double yr=max(L.p.y,L.q.y); if(sig(o.x-xl)>=0&&sig(xr-o.x)>=0&&sig(o.y-yl)>=0&&sig(yr-o.y)>=0) return 1; else return 0; } int banana(line u,line v) { point ret=u.p; double t=((u.p.x-v.p.x)*(v.p.y-v.q.y)-(u.p.y-v.p.y)*(v.p.x-v.q.x))/((u.p.x-u.q.x)*(v.p.y-v.q.y)-(u.p.y-u.q.y)*(v.p.x-v.q.x)); ret.x+=(u.q.x-u.p.x)*t; ret.y+=(u.q.y-u.p.y)*t; if(inside(ret,u)&&inside(ret,v)) return 1; return 0; } double det(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } //求多边形面积 double ploygon_area(int n) { double s=0.0; for(int i=1; i < n-1; i++) s += det(p[0],p[i],p[i+1]); return 0.5*fabs(s); } int main() { int i,n,ca=1,j,yy=0; while(scanf("%d",&n)!=EOF,n) { for(i=0; i<n; i++) scanf("%lf%lf",&p[i].x,&p[i].y); if(yy==1) printf(" "); yy=1; printf("Figure %d: ",ca++); if(n<3) { printf("Impossible "); continue; } p[n]=p[0]; int flag=0; for(i=0;i<n;i++) { for(j=i+2;j<n;j++) { if(i==(j+1)%n) continue; if(banana(line(p[i],p[i+1]),line(p[j],p[j+1]))) {flag=1;break;} } if(flag) break; } if(flag) { printf("Impossible "); continue; } double ans=ploygon_area(n); printf("%.2f ",ans); } return 0; }