zoj1010——Area
题意：求判断能否组成多边行，如果可以，求其面积。思路：
利用排斥和跨立判断是否线段相交；
求面积的话，用到测量师公式。
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;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.x *p.y -p.x *p.y;sum+=p.x *p.y-p.x *p.y ;if(sum<0) sum*=-1;return sum/2;}double mul(int yuan,int zhong ,int last){return (p.x -p.x )*(p.y-p.y )-(p.x -p.x )*(p.y-p.y );}bool inter(int a,int b,int c,int d){double x1=p.x;double y1=p.y;double x2=p.x;double y2=p.y;double x3=p.x ;double y3=p.y;double x4=p.x ;double y4=p.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.x >>p.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;}
页:
[1]