poj 1654 Area 多边形面积
题目描述：http://poj.org/problem?id=1654
题目大意：从平面坐标原点出发，1-9(除了5）表示不同的方向，最终保证回到原点，路径为一多边形，求多边形的面积。
解题思路：因为数据量较大，可以不用保存多边形的每个顶点信息，每次读一个数字（即读一段）就计算该线段与原点组成三角形的有向面积。
1.另外面积area 的保存用int 的话会溢出，所以选用long long(g++） 或__int64(vc6.0)。
2.dir 数组的设计方便求下一个点的坐标，想不到的话就直接switch语句 吧。
#include <iostream>#include <cstring>using namespace std;struct point { int x, y; point() { x = y = 0; }};int main() {int dir = {0,0,-1,-1,0,-1,1,-1,-1,0,0,0,1,0,-1,1,0,1,1,1}; char path; long long area; //用int 的话会溢出 int ncase; cin>>ncase; int len, num, i; point back, cur; while(ncase--) { area = 0; cin>>path; len = strlen(path); for(i = 0; i < len -1; i++) { num = path - '0'; cur.x = back.x + dir; cur.y = back.y + dir; area += back.y * cur.x - back.x * cur.y; back = cur; } if(area < 0) area = -area; if(area % 2 == 0) cout<<area / 2<<endl; else cout<<area / 2<<".5"<<endl; //.5需要特殊处理 } return 0;}
页:
[1]