题目描述: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[10][2] = {0,0,-1,-1,0,-1,1,-1,-1,0,0,0,1,0,-1,1,0,1,1,1}; char path[1000005]; 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[i] - '0'; cur.x = back.x + dir[num][0]; cur.y = back.y + dir[num][1]; 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; }
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj pku 1981 Circle and Points 点与圆 位置关系
2011-05-26 11:29 1261题目描述: http://poj.org/problem?id ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1210题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1026题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 871题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 883题目描述: http://acm.hdu.edu.cn/sh ... -
hdoj 1207 汉诺塔II dp 动态规划
2011-05-15 21:22 1666题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2506 Tiling 递推
2011-05-15 11:18 905题目描述: http://poj.org/problem?i ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1795题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1082题目描述: http://poj.org/problem?i ... -
poj 1012 Joseph
2011-05-10 17:42 1230题目描述:poj.org/problem?id=10 ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1130题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 798题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 713题目描述:http://www.poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 663题目描述:http://poj.org/problem?id= ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 542题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 750题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 835题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1212题目描述:http://poj.org/problem?id= ...
相关推荐
poj 1654的代码,供大家参考,看有没有更好的方法
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告