首页 > 代码库 > [ZOJ 1010] Area (计算几何)
[ZOJ 1010] Area (计算几何)
题目链接: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 (计算几何)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。