ITeye博客

winner, winner, chicken dinner

scott________ · 共 20 篇文章

poj pku 1981 Circle and Points 点与圆 位置关系

题目描述: http://poj.org/problem?id=1981 题目大意: 给定n 个点的坐标, 求单位圆最多可以覆盖(包括在圆上)多少个点. 题目分析: 假设某单位圆能覆盖最多点, 可以右移该单位圆, 使得恰有两个点(或更多)在圆上. 所以思路是,枚举以任意两点,以及半径为1 所确定的圆(有两个,总是选圆心在右, 或在左的那个圆)即可. #include <iostream> #include <cmath> using namespace std; #define eps 1e-6 struct Point { double x, y; Point() { x = y = 0.…

2011-05-26 11:29 · ACM解题报告 · 评论(0)

poj 1032 Parliament 数学

题目大意: 议会有N 个议员, 将他(她)们分成多组. 每次会议每组出一个代表, 且每次会议的代表都不完全相同. 求得一种分组情况, 使得能够开会的次数最多. 说白了就是求N 的一种划分 N = a1 + a2 + ... + a(t-1) + a(t), 使得M = a1 * a2 * ... * a(t - 1) * a(t) 最大. 关于该题的一些规则: 1 < a1 < 4; 假设a1 = 1; 那么一个数乘以a1, 乘积并不变大, 还不如把a1 加给其他元素。 假设a1 >= 4;那么a1 可以划分为2 和 (a1 - 2), 2 * (a1 - 2) 一定大于a1. 划分(假设升…

2011-05-25 17:34 · ACM解题报告 · 评论(0)

poj 1385 Lifting the Stone 多边形重心

题目描述: http://poj.org/problem?id=1012 题目分析: 该题就是给定多边形n 个顶点, 求重心 //IDE:vc6.0 #include <iostream> using namespace std; struct point { double x, y; }; double xmult(point p1,point p2,point p0){ return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } point barycenter(int n, point* p) { po…

2011-05-25 11:13 · ACM解题报告 · 评论(0)

poj 2676 Sudoku dfs 深搜

/************************************************************************/ /*思路: 先从后面开始搜,也就是从第八十个开始搜 1、如果一个小的方格内已经包含了非零的数,则继续向下搜 2、如果一个小的方格内是一个零数,也就是还没有放入相应的数,则对其从零到九开始尝试 3、对每一个数的尝试,检查其合法性:在其所在的3*3方格内是否合适;在此行是否合适:在此列是否合适 4、如果经过以上条件可以的话那么这个数字就可以放在此小方格上,然后继续进行搜索。 *************************************…

2011-05-16 21:05 · ACM解题报告 · 评论(0)

hdoj 2064 汉诺塔III 递推

题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=2064 (中文) 题目分析: 把n 个盘子从A 间接(不能把盘子直接从A 移到C )移到C 需要以下五步: 把n - 1 个盘子间接从A 移到C, f(n - 1) 把最大的盘子从A 移到B, 1 把n - 1 个盘子间接从C 移到A, f(n - 1) 把最大的盘子从B 移到C 1 把n - 1 个盘子间接从A 移到C, f(n - 1) 易得f(n) = 3 * f(n - 1) + 2, f(1) = 2; //编译器:vc6.0 #include <iostream> using nam…

2011-05-15 22:29 · ACM解题报告 · 评论(0)

hdoj 1207 汉诺塔II dp 动态规划

题目分析: 以下思路转自: http://yxq0620.blog.163.com/blog/static/4449439220102245168595/ 初看很难,理解了会发现真的很简单的... 不明白的建议看一下 http://poj.org/problem?id=1958 这题,里面有dp 的思路. 如果不明白就继续看吧. dp表示 将n个盘子通过4根柱子移动到目的柱子的最小的步数, f( i )表示 把 i个盘子通过 3根柱子移动到目的柱子的最小步数,f(i) 题目已经给出. dp =min(dp * 2 + f(n - i)); dp可以通过状态转移方程写出来,或许有的人看了状态转…

2011-05-15 21:22 · ACM解题报告 · 评论(0)

poj 2506 Tiling 递推

题目大意: 使用2 * 1 和 2 * 2 的矩形铺砌2 * n 的矩形, 共有多少种方法? 分析: 假设f ( n ) 为铺砌 2 * n 的矩形的方法种数, 参见下图: 易得 f ( n ) = f ( n - 1 ) + 2 * f ( n - 2 ); f ( 1 ) = 1; f ( 2 ) = 3; 又因为本体要求处理的n 很大, 需要大数处理, 故用Java 的BigInteger 类, 免去用c++ 实现大数加法, 代价是牺牲一部分的性能... 注意f ( 0 ) 的取值, 参见代码 import java.math.BigInteger; import java.util.…

2011-05-15 11:18 · ACM解题报告 · 评论(0)

poj 2420 A Star not a Tree? 多边形 费马点

题目大意: 其实是求n 边形的费马点, 即到n 边形的n 个顶点距离和最小的点, 该题要求计算出最小距离, 并四舍五入. 算法大意: 先拿一个点(该算法用n 个顶点的x, y 坐标和的均值所在的点)去计算距离和 最小值, 然后拿它的四个方向上的点去测试比较哪个点更优, 不断 迭代, 最终得到在精度允许下的费马点. #include <cstdio> #include <cmath> struct point { double x, y; point() { x = y = 0.0; } }; //返回两点间的距离 inline double mydistance(point p1, poin…

2011-05-14 18:57 · ACM解题报告 · 评论(0)

poj 2954 Triangle Pick 定理

题目大意: 给定顶点都是整数的三角形, 试求出该三角形内部的整点个数(不包括边界). 首先简要描述一下Pick 定理: 给定顶点坐标均是整点(或正方形格点)的简单多边形, Pick 定理说明了其面积S和内部格点数目i、边上格点数目b 的关系: S = i + b/2 - 1。 (其中i 表示多边形内部的点数,b 表示多边形边界上的点数,S 表示多边形的面积) Pick 定理在百度百科:<http://baike.baidu.com/view/3207200.html> 直接浙大模板之 #include <cstdio> #define abs(x) ((x)>0?(x):-(x)) stru…

2011-05-14 16:36 · ACM解题报告 · 评论(0)

poj 1012 Joseph

经典Joseph 问题的加强版, 参见注释, 注释很详细. #include /* 测试m是否满足要求 k: 有2k个人 m:每数到m就出局 */ bool test(int k, int m) { int i = 0, len = 2 * k; //len: 当前总人数 while(len > k) { i = (i + m - 1) % len; //每次出局人是出局前的len 个人中的第i 个, 下标从0 开始 if(i < k) return false; len--; //没出局一个,修改len } return true; } int main() { int k; int a[…

2011-05-10 17:42 · ACM解题报告 · 评论(0)

zoj 1081 Points Within 点与多边形关系

题目大意: n 边形的 n 个顶点按顺序给出, 接下来是m 个测试点, 对于每个测试点判断该点是否在多边形内(包括边界). 直接copy 浙大模板 O(∩_∩)O哈哈~ 附上代码 #include <cstdio> #include <cmath> #include <cstdlib> #define offset 10000 #define eps 1e-8 #define zero(x) ( ((x > 0) ? (x) : (-x)) < eps ) struct point { double x,y; }; struct line { point a,b; }; double xmu…

2011-05-07 17:51 · ACM解题报告 · 评论(0)

poj 1835 宇航员

题目描述: http://poj.org/problem?id=1835 该题关键在于方向的处理,代码注释比较详细。 #include <iostream> using namespace std; //辅助数组,完成当前坐标修改 int dir[6][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1, -1, 0, 0, 0, -1, 0, 0, 0, -1}; //方向数组,存储forward, right, up, //back, left, down相对应的方向值 int dir_pre[6] = {0, 1, 2 , 3, 4, 5}; int dir_cur[6] …

2011-05-03 17:00 · ACM解题报告 · 评论(0)

C/C++ 排序 总结 (够用就行,没有刻意追求标准)

函数原型: void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );//第四个参数可以缺省 base : 待排序数组的首地址 num :待排序元素的个数 size :每个元素的大小(byte), 用sizeof(a)即可,a为待排序数组 comparator: 比较函数指针 一个简单的调用:(a 为数组名,给十个元素排序) qsort(a, 10, seizeof(a)); //第四个参数默认,适用于基本类型的升序 qsort(a, 10,…

2011-04-25 17:38 · 评论(0)

poj 2398 Toy Storage

该题算是poj 2318 的加强版,poj 2318 的解题报告见: http://scott--------.iteye.com/blog/1013250 与2318 相比有一下不同: 1.输入的分割线无序 2.输出要求统计玩具的分布情况,假设m 个分区中都正好有t 个玩具, 要就输出m1: t1, m2: t2,...。按m 大小升序。 #include <cstdio> #include <algorithm> using namespace std; struct point { int x,y; }; struct line { point a,b; }; int xmult(li…

2011-04-23 20:19 · ACM解题报告 · 评论(0)

poj 1654 Area 多边形面积

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 p…

2011-04-23 20:10 · ACM解题报告 · 评论(0)