首页 > 其他 > 详细

poj 1654 Area(求多边形面积)

时间:2015-05-29 23:02:46      阅读:334      评论:0      收藏:0      [点我收藏+]

题意:从原点出发向八个方向走,所给数字串每个数字代表一个方向,终点与原点连线,求所得多边形面积;

思路:(性质)共起点的两向量叉积的一半为两向量围成三角形的面积。以此计算每条边首尾两个向量的叉积,求和,除二;

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double epsi=1e-10;
const double pi=acos(-1.0);
const int maxn=100005;
inline int sign(const double &x){
    if(x>epsi) return 1;
    if(x<-epsi) return -1;
    return 0;
}
struct point{
    long long x,y;
    point(double xx,double yy):x(xx),y(yy) {}
    point operator +(const point &op2) const{
        return point(x+op2.x,y+op2.y);
    }
    long long operator ^(const point &op2) const{
        return x*op2.y-y*op2.x;
    }
};
int main()
{
    int t,i,j,k;
    string s;
    long long ans;
    scanf("%d",&t);
    while(t--){
        cin>>s;
        ans=0;
        point p=point(0,0),p1=point(0,0);
        for(int i=0;i<s.size();i++){
            if(s[i]==1) p1=p+point(-1,-1);
            if(s[i]==2) p1=p+point(0,-1);
            if(s[i]==3) p1=p+point(1,-1);
            if(s[i]==4) p1=p+point(-1,0);
            if(s[i]==5) p1=p+point(0,0);
            if(s[i]==6) p1=p+point(1,0);
            if(s[i]==7) p1=p+point(-1,1);
            if(s[i]==8) p1=p+point(0,1);
            if(s[i]==9) p1=p+point(1,1);
            ans+=p^p1;
            p=p1;
        }
        if(ans<0) ans=-ans;
        printf("%lld",ans/2);
        if(ans%2) printf(".5");
        printf("\n");
    }
    return 0;
}

 

poj 1654 Area(求多边形面积)

原文:http://www.cnblogs.com/dashuzhilin/p/4539554.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!