zoj1010——Area

44424742

题意：求判断能否组成多边行，如果可以，求其面积。
思路：
利用排斥和跨立判断是否线段相交；
求面积的话，用到测量师公式。
http://episte.math.ntu.edu.tw/articles/sm/sm_25_10_1/page6.html
#include<iostream>#include<cstring>#include<cstdio>using namespace std;class point {public:double x,y;};point p[1005];double max(double a,double b){if(a>b) return a;else return b;}double min(double a,double b){if(a>b) return b;else return a;}int n;double area(){double sum=0;int i;for(i=1;i<n;i++)sum+=p[i-1].x *p[i].y -p[i].x *p[i-1].y;sum+=p[n-1].x *p[0].y-p[0].x *p[n-1].y ;if(sum<0) sum*=-1;return sum/2;}double mul(int yuan,int zhong ,int last){return (p[yuan].x -p[zhong].x )*(p[last].y-p[zhong].y )-(p[last].x -p[zhong].x )*(p[yuan].y-p[zhong].y );}bool inter(int a,int b,int c,int d){double x1=p[a].x;double y1=p[a].y;double x2=p[b].x;double y2=p[b].y;double x3=p[c].x ;double y3=p[c].y;double x4=p[d].x ;double y4=p[d].y;if(min(x1,x2)>max(x3,x4)) return false;if(min(x3,x4)>max(x1,x2)) return false;if(min(y1,y2)>max(y3,y4)) return false;if(min(y3,y4)>max(y1,y2)) return false;if(mul(c,a,b)*mul(d,a,b)>0) return false;if(mul(a,c,d)*mul(b,c,d)>0) return false;return true;}int main(){int i,j,ca=0;double ans;while(cin>>n&&n){bool flag=true;for(i=0;i<n;i++)cin>>p[i].x >>p[i].y;if(n<3)flag=false;else{for(i=0;i<=n-4;i++)for(j=i+2;j<=n-2;j++)if(inter(i,i+1,j,j+1)){flag=false;break;}if(flag){for(i=1;i<n-2;i++)if(inter(0,n-1,i,i+1)) { flag=false;break;}}if(flag)ans=area();}printf("Figure %d: \n",++ca);if(flag)printf("%.2f\n",ans);else printf("Impossible\n");}return 0;}