首页 > 代码库 > [ZOJ 1010] Area (计算几何)

[ZOJ 1010] Area (计算几何)

2024-08-03 04:12:48   222人阅读

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1010

题目大意：给你n个点，问你顺次连线能否连成多边形？如果能，就输出多边形面积。

 

面积用向量的叉积去算。然后能否连成多边形就是看这条线跟之前的线有没有交点。

这些在大白书上都有板子。。

 

代码：

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <string> 4 #include <iostream> 5 #include <cstring> 6 #include <algorithm> 7 #include <cctype> 8 #include <vector> 9 #include <map>10 #include <set>11 #include <iterator>12 #include <functional>13 #include <cmath>14 #include <numeric>15 #include <ctime>16 using namespace std;17 typedef long long LL;18 typedef pair<int,int> PII;19 typedef vector<int> VI;20 #define PB push_back21 #define MP make_pair22 #define SZ size()23 #define CL clear()24 #define AA first25 #define BB second26 #define EPS 1e-827 #define ZERO(x) memset((x),0,sizeof(x))28 const int INF = ~0U>>1;29 const double PI = acos(-1.0);30 31 struct POINT{32     double x,y;33     POINT(double ax=0,double ay=0):x(ax),y(ay) {}34 };35 typedef POINT VECTOR;36 37 POINT pts[1010];38 39 VECTOR operator- (POINT A,POINT B){40     return VECTOR(A.x-B.x,A.y-B.y);41 }42 43 double CROSS(VECTOR A,VECTOR B){44     return A.x*B.y-A.y*B.x;45 }46 47 double AREA(POINT *p,int n){48     double area = 0;49     for(int i=1;i<n-1;i++){50         area += CROSS(p[i]-p[0],p[i+1]-p[0]);51     }52     return area/2;53 }54 55 bool SegmentProperIntersection(POINT a1,POINT a2,POINT b1,POINT b2){56     double c1 = CROSS(a2-a1,b1-a1) , c2 = CROSS(a2-a1,b2-a1),57            c3 = CROSS(b2-b1,a1-b1) , c4 = CROSS(b2-b1,a2-b1);58     return c1*c2<EPS && c3*c4<EPS;59 }60 61 int main(){62     int n;63     int kase = 1;64     while( scanf("%d",&n), n ){65         if(kase!=1) puts("");66         bool flag = true;67         for(int i=0;i<n;i++){68             double a,b;69             scanf("%lf%lf",&a,&b);70             pts[i] = POINT(a,b);71             for(int j=0;j<i-2;j++){72                 if( SegmentProperIntersection(pts[j],pts[j+1],pts[i-1],pts[i])) flag = false;73             }74         }75         for(int j=1;j<n-2;j++){76             if( SegmentProperIntersection(pts[j],pts[j+1],pts[0],pts[n-1])) flag = false;77         }78         double area = fabs(AREA(pts,n));79         if( n==1||n==2 ){80             printf("Figure %d: Impossible\n",kase++);81             continue;82         }83         if(!flag) printf("Figure %d: Impossible\n",kase++);84         else printf("Figure %d: %.2f\n",kase++,area);85     }86     return 0;87 }

 

[ZOJ 1010] Area (计算几何)


联系
我们